hbhz_zcy @ 2022-10-13 20:27:39
其他人的帖子显示可能是少了splay，但我的每种操作都有对应旋转：
change,ask4 自带 splay，操作 1,3,4,5,6均使用。
操作2直接调用 splay。
尝试了在3，4，5后面加 splay 但是没用。
by hbhz_zcy @ 2022-10-13 20:29:32
//g++ -g l.cpp -o l -std=c++14 -O0 -Wall -fsanitize=undefined
//splay
#include<iostream>
#include<cstdio>
#include<cassert>
using namespace std;
const int maxn=2e6+10,maxh=2e9+10;
int N,M,ftop=0,root,lstans=0,ans=0;
struct node{int v,cnt,siz,l,r,fa;}f[maxn];
int qd(){
int rt=0,ng=0;char c=getchar();
while(c<'0'||c>'9') ng^=c=='-',c=getchar();
while('0'<=c&&c<='9') rt=(rt<<3)+(rt<<1)+c-48,c=getchar();
return ng?-rt:rt;
}
void pushup(int t){if(t) f[t].siz=f[t].cnt+f[f[t].l].siz+f[f[t].r].siz;}
int flson(int t){return f[t].fa?f[f[t].fa].l==t:-1;}
void zlg(int t){
if(!(t&&f[t].r)) return;
int fa=f[t].fa,rson=f[t].r;
if(fa) flson(t)?f[fa].l=f[t].r:f[fa].r=f[t].r;
f[t].fa=rson,f[rson].fa=fa;if(f[rson].l) f[f[rson].l].fa=t;
f[t].r=f[rson].l,f[rson].l=t;
pushup(t),pushup(rson);
}
void zrg(int t){
if(!(t&&f[t].l)) return;
int fa=f[t].fa,lson=f[t].l;
if(fa) flson(t)?f[fa].l=f[t].l:f[fa].r=f[t].l;
f[t].fa=lson,f[lson].fa=fa;if(f[lson].r) f[f[lson].r].fa=t;
f[t].l=f[lson].r,f[lson].r=t;
pushup(t),pushup(lson);
}
void splay(int t){
while(f[t].fa){
if(flson(t)){if(flson(f[t].fa)==1) zrg(f[f[t].fa].fa);zrg(f[t].fa);}
else{if(flson(f[t].fa)==0) zlg(f[f[t].fa].fa);zlg(f[t].fa);}
}
root=t;
}
int change(int t,int v){
if(!t) return 0;
f[t].siz++;
if(v==f[t].v){f[t].cnt++;splay(t);}
else if(v<f[t].v){if(!change(f[t].l,v)){f[f[t].l=++ftop]={v,1,1,0,0,t};splay(ftop);}}
else if(v>f[t].v){if(!change(f[t].r,v)){f[f[t].r=++ftop]={v,1,1,0,0,t};splay(ftop);}}
return 1;
}
int askt(int t,int v){
if(!t) return maxh;
if(v==f[t].v) return t;
int rt=askt(v<f[t].v?f[t].l:f[t].r,v);
return rt==maxh?t:rt;
}
void ers(int t){
if(!f[t].l){root=f[t].r;return;}
if(!f[t].r){root=f[t].l;return;}
f[f[t].l].fa=0;splay(askt(f[t].l,maxh));
f[root].r=f[t].r,f[f[t].r].fa=root;
}
void ask4(int t,int v){
if(v<=f[f[t].l].siz) return ask4(f[t].l,v);
else if(v<=f[f[t].l].siz+f[t].cnt) return splay(t);
return ask4(f[t].r,v-f[f[t].l].siz-f[t].cnt);
}
int ask5(int t){
if(!t) return maxh;
int rt=ask5(f[t].r);
return rt==maxh?f[t].v:rt;
}
int ask6(int t){
if(!t) return maxh;
int rt=ask6(f[t].l);
return rt==maxh?f[t].v:rt;
}
void debug(int t){
if(!t){putchar('\n');return;}
printf("vis %d:v=%d,cnt=%d,siz=%d,l=%d,r=%d,fa=%d\n",t,f[t].v,f[t].cnt,f[t].siz,f[t].l,f[t].r,f[t].fa);
debug(f[t].l);debug(f[t].r);
printf("leave %d\n",t);
}
int main(){
// freopen("in.txt","r",stdin);
N=qd(),M=qd();f[root=++ftop]={maxh,1,2,2,0,0},f[++ftop]={-maxh,1,1,0,0,1};
for(int i=1;i<=N;i++) change(root,qd());
while(M--){
int t=qd(),x=qd()^lstans;
if(t==1) change(root,x);
else if(t==2){splay(askt(root,x));f[root].siz--;if(!--f[root].cnt) ers(root);}
else if(t==3){change(root,x);ans^=lstans=f[f[root].l].siz;f[root].siz--;if(!--f[root].cnt) ers(root);}
else if(t==4){ask4(root,x+1);ans^=lstans=f[root].v;}
else if(t==5){change(root,x);ans^=lstans=ask5(f[root].l);f[root].siz--;if(!--f[root].cnt) ers(root);}
else if(t==6){change(root,x);ans^=lstans=ask6(f[root].r);f[root].siz--;if(!--f[root].cnt) ers(root);}
else if(t<0) return 0;
else debug(root);
}
printf("%d\n",ans);
return 0;
}by hbhz_zcy @ 2022-10-13 20:37:17
我随机选一个点进行splay然后它AC了
不过还是上面的问题没有解决。