关于SBT的TLE

rt,TLE 19，20 点。
考虑到纯size不好，我搞了一个只记录节点个数的size，然后TLE更多了。

//g++ -g m.cpp -o m -std=c++14 -O0 -Wall -fsanitize=undefined
//SBT
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=2e6+10,maxh=2e9+10;
int N,M,ftop=0,root=1,lstans=0,ans=0;
struct node{int l,r,v,siz,cnt,siz01;}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 debug(int t){
    printf("ask %d:l=%d r=%d v=%d siz=%d cnt=%d\n",t,f[t].l,f[t].r,f[t].v,f[t].siz,f[t].cnt);
    if(f[t].l){printf("%d->L\n",t);debug(f[t].l);}
    if(f[t].r){printf("%d->R\n",t);debug(f[t].r);}
}
void pushup(int t){f[t].siz=f[f[t].l].siz+f[t].cnt+f[f[t].r].siz,f[t].siz01=f[f[t].l].siz01+f[f[t].r].siz01+1;}
void zig(int &t){
    int _l=f[t].l;
    f[t].l=f[_l].r,f[_l].r=t;
    pushup(t);pushup(t=_l);
}
void zag(int &t){
    int _r=f[t].r;
    f[t].r=f[_r].l,f[_r].l=t;
    pushup(t);pushup(t=_r);
}
void change1(int &t,int v){
    if(!t){f[t=++ftop]={0,0,v,1,1,1};return;}
    if(v==f[t].v)  f[t].cnt++;
    else if(v<f[t].v)  change1(f[t].l,v);
    else if(v>f[t].v)  change1(f[t].r,v);
    pushup(t);
}
void change2(int &t,int v){
    if(!t)  return;
    if(v==f[t].v){
        if(f[t].cnt>1)  f[t].cnt--;
        else{
            f[t].siz01--;
            if(!f[t].l||!f[t].r)  t=f[t].l+f[t].r;
            else if(f[f[t].l].siz01>f[f[t].r].siz01)  zig(t),change2(f[t].r,v);
            else zag(t),change2(f[t].l,v);
        }
    }
    else change2(v<f[t].v?f[t].l:f[t].r,v);
    pushup(t);
}
int ask3(int t,int v){
    if(!t)  return 1;
    if(v<f[t].v)  return ask3(f[t].l,v);
    if(v>f[t].v)  return f[f[t].l].siz+f[t].cnt+ask3(f[t].r,v);
    return f[f[t].l].siz+1;
}
int ask4(int t,int v){
    if(!t)  return 0;
    if(v<=f[f[t].l].siz)  return ask4(f[t].l,v);
    if(v>f[f[t].l].siz+f[t].cnt)  return ask4(f[t].r,v-f[f[t].l].siz-f[t].cnt);
    return f[t].v;
}
int ask5(int t,int v){
    int rt;
    while(t){
        if(f[t].v<v)  rt=f[t].v,t=f[t].r;
        else t=f[t].l;
    }
    return rt;
}
int ask6(int t,int v){
    int rt;
    while(t){
        if(f[t].v>v)  rt=f[t].v,t=f[t].l;
        else t=f[t].r;
    }
    return rt;
}
void sbt(int &t,int v){
    if(!t||f[t].v==v)  return;
    sbt(v<f[t].v?f[t].l:f[t].r,v);
    if(f[t].l&&f[f[t].l].siz01>f[f[t].r].siz01+1)  zig(t);
    else if(f[t].r&&f[f[t].l].siz01+1<f[f[t].r].siz01)  zag(t);
}
int main(){
    freopen("in.txt","r",stdin);
    N=qd(),M=qd();f[root=++ftop]={2,0,maxh,2,1,1},f[++ftop]={0,0,-maxh,1,1,1};
    for(int i=1;i<=N;i++)  change1(root,qd());
    while(M--){
        int x=qd(),y=qd()^lstans;
        if(x==1)  change1(root,y);
        else if(x==2)  change2(root,y);
        else if(x==3)  lstans=ask3(root,y)-1;
        else if(x==4)  lstans=ask4(root,y+1);
        else if(x==5)  lstans=ask5(root,y);
        else if(x==6)  lstans=ask6(root,y);
        else debug(root);
        if(x>2) ans^=lstans;
        sbt(root,y);
    }
    printf("%d\n",ans);
    return 0;
}

如果您会splay,也可以看这一篇