先把板子放在这里,以后忘了就回来看(
这份代码在P6136 【模板】普通平衡树(数据加强版)能跑到长达最优解四倍的时间。
果然人蒻常数巨大。
#include <bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
int n,m,ans,last;
inline int read()
{
char ch;int res=0;
for(ch=getchar();isspace(ch);ch=getchar());
for(;isdigit(ch);res=res*10+ch-'0',ch=getchar());
return res;
}
struct TreeNode
{
int val,cnt,siz;
TreeNode *ch[2],*fa;
TreeNode(int v): val(v)
{
cnt=siz=1;
ch[0]=ch[1]=fa=NULL;
}
}*rt;
typedef TreeNode *pNode;
inline bool which(pNode i)
{ return i==i->fa->ch[1]; }
inline void pushup(pNode i)
{
i->siz=i->cnt;
if(i->ch[0]) i->siz+=i->ch[0]->siz;
if(i->ch[1]) i->siz+=i->ch[1]->siz;
}
inline void rotate(pNode i)
{
pNode f=i->fa,gf=i->fa->fa;
bool x=which(i);
i->fa=gf;
if(gf) gf->ch[which(f)]=i;
f->ch[x]=i->ch[!x];
if(f->ch[x]) f->ch[x]->fa=f;
i->ch[!x]=f,f->fa=i;
pushup(f),pushup(i);
}
inline void splay(pNode x,pNode y=NULL)
{
for(pNode f;(f=x->fa)!=y;rotate(x))
if(f->fa!=y)
rotate(which(x)==which(f)?f:x);
if(!y) rt=x;
}
void insert(int x,pNode &i=rt,pNode f=nullptr)
{
if(!i) i=new TreeNode(x),i->fa=f,splay(i);
else
{
i->siz++;
if(i->val==x) i->cnt++,i->siz++,splay(i);
else if(x<i->val) insert(x,i->ch[0],i);
else insert(x,i->ch[1],i);
}
}
void remove(int x)
{
pNode i=rt,j;
while(i->val!=x)
if(x<i->val) i=i->ch[0];
else i=i->ch[1];
splay(i);
if(--rt->siz,--rt->cnt) return;
if(!rt->ch[0])
{ j=rt,rt=rt->ch[1];delete j; }
else if(!rt->ch[1])
{ j=rt,rt=rt->ch[0];delete j; }
else
{
j=i->ch[0];
for(;j->ch[1];j=j->ch[1]);
splay(j);
j->ch[1]=i->ch[1],i->ch[1]->fa=j;
delete i;
}
}
int askValue(int k,pNode &i=rt)
{
int sz=i->ch[0]?i->ch[0]->siz:0;
if(k<=sz)
return askValue(k,i->ch[0]);
else
{
k-=sz;
if(k<=i->cnt) return i->val;
else return askValue(k-i->cnt,i->ch[1]);
}
}
int askRank(int x,pNode i=rt)
{
if(!i) return 1;
int sz=i->ch[0]?i->ch[0]->siz:0;
if(x==i->val) return sz+1;
else if(x<i->val) return askRank(x,i->ch[0]);
else return sz+i->cnt+askRank(x,i->ch[1]);
}
int getPre(int x)
{
pNode i=rt;int res=-INF;
while(i)
{
if(i->val>=x) i=i->ch[0];
else res=i->val,i=i->ch[1];
}
return res;
}
int getNxt(int x)
{
pNode i=rt;int res=INF;
while(i)
{
if(i->val<=x) i=i->ch[1];
else res=i->val,i=i->ch[0];
}
return res;
}
void debug(pNode &i=rt)
{
if(!i) return;
debug(i->ch[0]);
for(int j=1;j<=i->cnt;j++)
printf("%d ",i->val);
debug(i->ch[1]);
if(i==rt) puts("");
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) insert(read());
insert(-INF),insert(INF);
while(m--)
{
int opt,x;
opt=read(),x=read()^last;
if(opt==1) insert(x);
else if(opt==2) remove(x);
else if(opt==3) ans^=(last=askRank(x)-1);
else if(opt==4) ans^=(last=askValue(x+1));
else if(opt==5) ans^=(last=getPre(x));
else ans^=(last=getNxt(x));
}
printf("%d",ans);
return 0;
}