4.24 省选模拟赛欧珀瑞特主席树可持久化trie树

很容易的一道题目。大概。不过我空间计算失误MLE了我草草的计算了一下没想到GG了。

关键的是我学了一个dalao的空间回收的方法但是弄巧成拙了。

题目没有明确指出在任意时刻数组长度为有限制什么的况且这道题也不卡空间 nlogn或者再大一倍的空间都是可以过的。

但是我仍然作死写了两个队列进行空间的回收 (我也不知道我在干什么。

(可能完全觉得好玩吧)

开的空间大小：\(\frac{10\cdot 30\cdot 500000\cdot 4}{1000000}=600MB\)

所以GG了。值得一提的是考试的时候没有多想直接主席树+可持久化trie了。

其实光可持久化trie树也是可以求区间第k大和区间<=x的数的个数的。

const int MAXN=500010;

int n,m,maxx,id,ans,mark;

int a[MAXN];

int rt1[MAXN],rt2[MAXN],pos1[MAXN*20],pos2[MAXN*20];

struct wy{int l,r,sum;}t[MAXN*20];

struct jl{int c[2],sz;}s[MAXN*30];

queue<int>q1,q2;

inline int getnum1()

{

	int w=q1.front();q1.pop();

	l(w)=r(w)=sum(w)=0;

	return w;

}

inline int getnum2()

{

	int w=q2.front();q2.pop();

	sz(w)=s[w].c[0]=s[w].c[1]=0;

	return w;

}

inline void insert(int &p,int las,int l,int r,int x)

{

	p=getnum1();pos1[p]=id;t[p]=t[las];

	if(l==r){++sum(p);return;}

	int mid=(l+r)>>1;

	if(x<=mid)insert(l(p),l(las),l,mid,x);

	else insert(r(p),r(las),mid+1,r,x);

	sum(p)=sum(l(p))+sum(r(p));

}

inline void build(int &p,int las,int depth,int x)

{

	p=getnum2();pos2[p]=id;s[p]=s[las];

	if(!depth){++sz(p);return;}

	int w=(x&(1<<(depth-1)))?1:0;

	build(s[p].c[w],s[las].c[w],depth-1,x);

	sz(p)=sz(s[p].c[0])+sz(s[p].c[1]);

}

inline void ask1(int p,int las,int depth,int x)

{

	if(!depth)return;

	int w=(x&(1<<(depth-1)))?1:0;

	if(sz(s[p].c[w^1])-sz(s[las].c[w^1])>0)

	{

		if(w^1)ans=ans|(1<<(depth-1));

		ask1(s[p].c[w^1],s[las].c[w^1],depth-1,x);

	}

	else

	{

		if(w)ans=ans|(1<<(depth-1));

		ask1(s[p].c[w],s[las].c[w],depth-1,x);

	}

}

inline void del1(int &p)

{

	if(!p)return;

	if(pos1[p]==mark)

	{

		del1(l(p));

		del1(r(p));

		q1.push(p);p=0;

	}

	return;

}

inline void del2(int &p)

{

	if(!p)return;

	if(pos2[p]==mark)

	{

		del2(s[p].c[0]);

		del2(s[p].c[1]);

		q2.push(p);p=0;

	}

	return;

}

inline int ask(int p,int las,int l,int r,int x)

{

	if(r<=x)return sum(p)-sum(las);

	int mid=(l+r)>>1;

	if(x>mid)return ask(l(p),l(las),l,mid,x)+ask(r(p),r(las),mid+1,r,x);

	return ask(l(p),l(las),l,mid,x);

}

inline int query(int p,int las,int l,int r,int x)

{

	if(l==r)return l;

	int mid=(l+r)>>1;

	int ww=sum(l(p))-sum(l(las));

	if(ww>=x)return query(l(p),l(las),l,mid,x);

	return query(r(p),r(las),mid+1,r,x-ww);

}

int main()

{

	freopen("operator.in","r",stdin);

	freopen("operator.out","w",stdout);

	get(m);maxx=500010;

	rep(1,20*MAXN,i)q1.push(i),q2.push(i);

	rep(1,m,i)

	{

		int op,x,y,z;

		get(op)+1;get(x);

		if(op==1)

		{

			a[++n]=x;id=n;

			insert(rt1[n],rt1[n-1],1,maxx,x);

			build(rt2[n],rt2[n-1],21,x);

		}

		if(op==2)

		{

			get(y);get(z);ans=0;

			ask1(rt2[y],rt2[x-1],21,z);

			put(ans);

		}

		if(op==3)

		{

			fep(n,n-x+1,j)

			{

				mark=j;

				del1(rt1[j]);

				del2(rt2[j]);

			}

			n=n-x;

		}

		if(op==4)

		{

			get(y);get(z);

			put(ask(rt1[y],rt1[x-1],1,maxx,z));

		}

		if(op==5)

		{

			get(y);get(z);

			put(query(rt1[y],rt1[x-1],1,maxx,z));

		}

	}

	return 0;

}

巴特西

4.24 省选模拟赛欧珀瑞特主席树可持久化trie树

最新文章

热门文章

巴特西

4.24 省选模拟赛 欧珀瑞特 主席树 可持久化trie树

最新文章

热门文章

4.24 省选模拟赛欧珀瑞特主席树可持久化trie树