Split @ 2022-09-19 13:59:04
Unaccepted 92
TLE #5,#6
by Split @ 2022-09-19 13:59:33
#include<cstdio>
using namespace std;
int re()
{
int s=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s*f;
}
void wr(int s)
{
if(s<0)putchar('-'),s=-s;
if(s>9)wr(s/10);
putchar(s%10+48);
}
const int inf=2e6+7;
int n,m,last,ans,a[inf];
struct splay{
int fa,hz[2];
int siz,cnt,val;
}T[inf],q0;
int rot,cnt;
void clear(int i){T[i]=q0;}
void pushup(int i){T[i].siz=T[T[i].hz[0]].siz+T[T[i].hz[1]].siz+T[i].cnt;}
bool pd(int i){return i==T[T[i].fa].hz[1];}
void rotate(int i)
{
int fa=T[i].fa,gf=T[fa].fa;
int pdi=pd(i),pdf=pd(fa);
T[i].fa=gf;if(gf)T[gf].hz[pdf]=i;
if(T[i].hz[pdi^1])T[T[i].hz[pdi^1]].fa=fa;
T[fa].hz[pdi]=T[i].hz[pdi^1];
T[fa].fa=i,T[i].hz[pdi^1]=fa;
pushup(fa),pushup(i);
}
void splay(int i,int to)
{
to=T[to].fa;
for(int fa=T[i].fa;fa!=to;rotate(i),fa=T[i].fa)
if(T[fa].fa^to)rotate((pd(i)^pd(fa))?i:fa);
if(!to)rot=i;
}
int new_(int k,int fa)
{
T[++cnt].val=k,T[cnt].fa=fa;
T[cnt].siz=T[cnt].cnt=1;
return cnt;
}
void insert(int k)
{
if(!rot){rot=new_(k,0);return;}
int now=rot,fa=0;
while(now)
{
if(k==T[now].val)
{
T[now].cnt++,T[now].siz++;
splay(now,rot);return;
}
fa=now;
if(k<T[now].val)now=T[now].hz[0];
else now=T[now].hz[1];
}
now=new_(k,fa);
T[fa].hz[k>T[fa].val]=now;
splay(now,rot);
}
int ask_rnk(int k)
{
int now=rot,ans=0;
while(now)
{
if(T[now].val==k)
{
int ret=T[T[now].hz[0]].siz;
splay(now,rot);
return ans+ret+1;
}
if(k<T[now].val)now=T[now].hz[0];
else ans+=T[T[now].hz[0]].siz+T[now].cnt,now=T[now].hz[1];
}
return ans+1;
}
int ask_kth(int k)
{
int now=rot;
while(1)
{
if(T[T[now].hz[0]].siz+1<=k&&k<=T[T[now].hz[0]].siz+T[now].cnt)
{splay(now,rot);return T[now].val;}
if(k<=T[T[now].hz[0]].siz)now=T[now].hz[0];
else k-=T[T[now].hz[0]].siz+T[now].cnt,now=T[now].hz[1];
}
}
int pre()
{
int now=T[rot].hz[0];
if(now)while(T[now].hz[1])
now=T[now].hz[1];
return now;
}
int nex()
{
int now=T[rot].hz[1];
if(now)while(T[now].hz[0])
now=T[now].hz[0];
return now;
}
void remove(int k)
{
ask_rnk(k);int now=rot;
if(T[now].cnt>1){T[now].cnt--,T[now].siz--;return;}
if(T[now].hz[0]+T[now].hz[1]==0){clear(now),rot=0;return;}
if(T[now].hz[0]==0)
{
rot=T[now].hz[1];T[rot].fa=0;
pushup(rot);return;
}
if(T[now].hz[1]==0)
{
rot=T[now].hz[0];T[rot].fa=0;
pushup(rot);return;
}
int ls=pre();
splay(ls,rot);
T[rot].hz[1]=T[now].hz[1];
T[T[now].hz[1]].fa=rot;
clear(now);pushup(rot);
}
int ask_pre(int k)
{
insert(k);int ret=T[pre()].val;
remove(k);return ret;
}
int ask_nex(int k)
{
insert(k);int ret=T[nex()].val;
remove(k);return ret;
}
int main()
{
n=re();m=re();
for(int i=1;i<=n;i++)
a[i]=re(),insert(a[i]);
while(m--)
{
int op=re(),k=re()^last;
if(op==1)insert(k);
if(op==2)remove(k);
if(op==3)last=ask_rnk(k),ans^=last;
if(op==4)last=ask_kth(k),ans^=last;
if(op==5)last=ask_pre(k),ans^=last;
if(op==6)last=ask_nex(k),ans^=last;
}
wr(ans);
return 0;
}by w23c3c3 @ 2022-09-19 14:45:14
rnk 和 kth 没 splay。
by Split @ 2022-09-19 14:47:02
@w23c3c3 我在 return 之前 splay 了啊
by w23c3c3 @ 2022-09-19 14:47:56
o。
但是你在 askrank 的时候假如一直到最后了那你不是就没 splay 了嘛。
by Split @ 2022-09-19 14:49:03
@w23c3c3 没看懂qwq
by w23c3c3 @ 2022-09-19 14:54:54
就是你这个 askrank 不是有个 while 嘛，然后跑满了这个 while 你就返回 ans+1 了，那他就可以一直跑满这个 while 吧。
by Split @ 2022-09-19 16:34:19
@w23c3c3 可是我这样也是 T qwq
const int inf=2e6+7;
int n,m,last,ans,a[inf];
struct splay{
int fa,hz[2];
int siz,cnt,val;
}T[inf],q0;
int rot,cnt;
void clear(int i){T[i]=q0;}
void pushup(int i){T[i].siz=T[T[i].hz[0]].siz+T[T[i].hz[1]].siz+T[i].cnt;}
bool pd(int i){return i==T[T[i].fa].hz[1];}
void rotate(int i)
{
int fa=T[i].fa,gf=T[fa].fa;
int pdi=pd(i),pdf=pd(fa);
T[i].fa=gf;if(gf)T[gf].hz[pdf]=i;
if(T[i].hz[pdi^1])T[T[i].hz[pdi^1]].fa=fa;
T[fa].hz[pdi]=T[i].hz[pdi^1];
T[fa].fa=i,T[i].hz[pdi^1]=fa;
pushup(fa),pushup(i);
}
void splay(int i,int to)
{
to=T[to].fa;
for(int fa=T[i].fa;fa!=to;rotate(i),fa=T[i].fa)
if(T[fa].fa^to)rotate((pd(i)^pd(fa))?i:fa);
if(!to)rot=i;
}
int new_(int k,int fa)
{
T[++cnt].val=k,T[cnt].fa=fa;
T[cnt].siz=T[cnt].cnt=1;
return cnt;
}
void insert(int k)
{
if(!rot){rot=new_(k,0);return;}
int now=rot,fa=0;
while(now)
{
if(k==T[now].val)
{
T[now].cnt++,T[now].siz++;
splay(now,rot);return;
}
fa=now;
if(k<T[now].val)now=T[now].hz[0];
else now=T[now].hz[1];
}
now=new_(k,fa);
T[fa].hz[k>T[fa].val]=now;
splay(now,rot);
}
int rnk(int k)
{
int now=rot,ans=0;
while(1)
{
if(T[now].val==k)
{
int ret=T[T[now].hz[0]].siz;
splay(now,rot);
return ans+ret+1;
}
if(k<T[now].val)now=T[now].hz[0];
else ans+=T[T[now].hz[0]].siz+T[now].cnt,now=T[now].hz[1];
}
}
int ask_kth(int k)
{
int now=rot;
while(1)
{
if(T[T[now].hz[0]].siz+1<=k&&k<=T[T[now].hz[0]].siz+T[now].cnt)
{splay(now,rot);return T[now].val;}
if(k<=T[T[now].hz[0]].siz)now=T[now].hz[0];
else k-=T[T[now].hz[0]].siz+T[now].cnt,now=T[now].hz[1];
}
}
int pre()
{
int now=T[rot].hz[0];
if(now)while(T[now].hz[1])
now=T[now].hz[1];
return now;
}
int nex()
{
int now=T[rot].hz[1];
if(now)while(T[now].hz[0])
now=T[now].hz[0];
return now;
}
void remove(int k)
{
rnk(k);int now=rot;
if(T[now].cnt>1){T[now].cnt--,T[now].siz--;return;}
if(T[now].hz[0]+T[now].hz[1]==0){clear(now),rot=0;return;}
if(T[now].hz[0]==0)
{
rot=T[now].hz[1];T[rot].fa=0;
pushup(rot);return;
}
if(T[now].hz[1]==0)
{
rot=T[now].hz[0];T[rot].fa=0;
pushup(rot);return;
}
int ls=pre();
splay(ls,rot);
T[rot].hz[1]=T[now].hz[1];
T[T[now].hz[1]].fa=rot;
clear(now);pushup(rot);
}
int ask_rnk(int k)
{
insert(k);int ret=rnk(k);
remove(k);return ret;
}
int ask_pre(int k)
{
insert(k);int ret=T[pre()].val;
remove(k);return ret;
}
int ask_nex(int k)
{
insert(k);int ret=T[nex()].val;
remove(k);return ret;
}
int main()
{
n=re();m=re();
for(int i=1;i<=n;i++)
a[i]=re(),insert(a[i]);
while(m--)
{
int op=re(),k=re()^last;
if(op==1)insert(k);
if(op==2)remove(k);
if(op==3)last=ask_rnk(k),ans^=last;
if(op==4)last=ask_kth(k),ans^=last;
if(op==5)last=ask_pre(k),ans^=last;
if(op==6)last=ask_nex(k),ans^=last;
}
wr(ans);
return 0;
}by Split @ 2022-09-19 16:35:31
我好像还是没有理解您的意思，所以应该怎么 Splay ？qwq
by Split @ 2022-09-19 17:00:20
找到原因了，pre 和 nex 没有 splay……，留此贴以警示后人
by C_liar @ 2022-12-03 10:18:14
@Split 感谢大佬%%%%%