刘子瑞 @ 2020-08-25 17:49:33
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<ctime>
using namespace std;
const int MAXN=2e6+10;
int M,N,tot,root;
struct TREE
{
int key,ra,lson,rson,size;
}tree[MAXN];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
int newpoint(int x)
{
tot++;
tree[tot].key=x;
tree[tot].ra=rand();
tree[tot].size=1;
}
void update(int a)
{
tree[a].size=1 + (tree[tree[a].lson].size + tree[tree[a].rson].size);
return ;
}
void split(int a,int num,int &l,int &r)
{
if( !a )
{
l=r=0;
return ;
}
if(tree[a].key <= num )
{
l=a;
split(tree[a].rson,num,tree[a].rson,r);
}
else
{
r=a;
split(tree[a].lson,num,l,tree[a].lson);
}
update(a);
return ;
}
int merge(int d1,int d2)
{
if( !d1 || !d2 ) return d1+d2;
if( tree[d1].ra < tree[d2].ra )
{
tree[d2].lson=merge(d1,tree[d2].lson);
update(d2);
return d2;
}
else
{
tree[d1].rson=merge(tree[d1].rson,d2);
update(d1);
return d1;
}
}
void insert(int x)
{
newpoint(x);
int l=0,r=0;
split(root,x-1,l,r);
l=merge(l,tot);
root=merge(l,r);
return ;
}
void delet(int x)
{
int l=0,r=0,del=0;
split(root,x,l,r);
split(l,x-1,l,del);
del=merge(tree[del].lson,tree[del].rson);
l=merge(l,del);
root=merge(l,r);
return ;
}
int Queryrank(int x)
{
int l=0,r=0;
split(root,x-1,l,r);
int ans=tree[l].size+1;
root=merge(l,r);
return ans;
}
int Querynum(int rankx)
{
int a=root;
while(a)
{
if( tree[a].size == 1 ) return tree[a].key ;
if( tree[tree[a].lson].size >= rankx ) a=tree[a].lson;
else
{
rankx-=tree[tree[a].lson].size;
if(rankx==1) return tree[a].key;
rankx--;
a=tree[a].rson;
}
}
}
int Querypre(int x)
{
int l=0,r=0;
split(root,x-1,l,r);
int pos=l;
while( tree[pos].rson ) pos=tree[pos].rson;
root=merge(l,r);
return tree[pos].key;
}
int Queryneg(int x)
{
int l=0,r=0;
split(root,x,l,r);
int pos=r;
while( tree[pos].lson ) pos=tree[pos].lson;
root=merge(l,r);
return tree[pos].key;
}
int main()
{
//freopen("P6136_1.in","r",stdin);
srand(time(0));
//scanf("%d%d",&N,&M);
N=read();M=read();
for(int i=1;i<=N;i++)
{
int shu;
//scanf("%d",&shu);
shu=read();
insert(shu);
}
int ANS=0,LAST=0;
for(int item=1;item<=M;item++)
{
int cmd,shu;
//scanf("%d%d",&cmd,&shu);
cmd=read();shu=read();
shu=shu^LAST;
if(cmd==1) insert(shu);
else if(cmd==2) delet(shu);
else if(cmd==3) LAST=Queryrank(shu),ANS^=LAST;
else if(cmd==4) LAST=Querynum(shu),ANS^=LAST;
else if(cmd==5) LAST=Querypre(shu),ANS^=LAST;
else if(cmd==6) LAST=Queryneg(shu),ANS^=LAST;
}
printf("%d\n",ANS);
return 0;
}
求dalao查错
by lemir3 @ 2020-08-25 18:06:51
orz lzr
by Social_Zhao @ 2020-08-25 18:16:58
orz lzr