3721求调

#include<bits/stdc++.h>
#define sdn cout
#define ll long long
#define vi vector<int>
#define ld double
#define vl vector<ll>
#define mpair make_pair
#define pb push_back
using namespace std;
mt19937_64 rnd(time(nullptr));
int read(){
    int x = 0,f = 1;
    char ch = getchar();
    while(ch < 48 && ch > 57){
        if(ch == '-')  f = -1;
        ch = getchar();
    }
    while(ch >= 48 && ch <= 57){
        x  = x<<3 + x<<1 + ch-48;
        ch = getchar();
    }
    return x*f;
}
void write(int x){
    if(x < 0)  putchar('-'),x = -x;
    if(x > 9)  write(x/10);
    putchar(x%10+48);
}
const int N = 1e6 + 10,M = 1e6 + 10,INF = INT_MAX;

int n,m,T,a[N],b[N],k,cnt,rt,stk[N];
ll ans;
int q[N][2],fa[N],c[N][2],cnt1,cnt2;
set <int> S;
#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
#define isrt(x)  (ls(tr[x].f) != x && rs(tr[x].f) != x)
struct node{
    int f,s[2],tg,siz;
}tr[N];
void pu(int p){
    tr[p].siz = tr[ls(p)].siz + tr[rs(p)].siz + 1;
}
void pd(int p){
    if(tr[p].tg){
        swap(ls(p),rs(p));
        tr[ls(p)].tg ^= 1;
        tr[rs(p)].tg ^= 1;
        tr[p].tg = 0;
    }
}
void rotate(int x){
    int y = tr[x].f,z = tr[y].f;
    int k = ls(y)==x;
    if(!isrt(y))  tr[z].s[rs(z)==y] = x;
    tr[x].f = z;
    tr[tr[x].s[k]].f = y;
    tr[y].s[k^1] = tr[x].s[k];
    tr[x].s[k] = y;
    tr[y].f = x;
    pu(y),pu(x);
}
void splay(int x){
    int u = x,tp = 0;
    stk[++tp] = u;
    while(!isrt(u))  u = tr[u].f,stk[++tp] = u;
    while(tp)  pd(stk[tp--]);
    while(!isrt(x)){
        int y = tr[x].f,z = tr[y].f;
        if(!isrt(y))  (ls(y)==x^ls(z)==y)?rotate(x):rotate(y);
        rotate(x);
    }
}
void acc(int x){
    int y = 0;
    while(x){
        splay(x);
        rs(x) = y;pu(x);
        y = x;x = tr[x].f;
    }
}
void mkrt(int x){
    acc(x);splay(x);tr[x].tg ^= 1;
}
void split(int x,int y){
    mkrt(x);acc(y);splay(y);
}
void link(int x,int y){
    if(!x||!y)  return ;
    mkrt(x);
    tr[x].f = y;
}
void cut(int x,int y){
    if(!x||!y)  return ;
    split(x,y);
    tr[x].f = ls(y) = 0;pu(x),pu(y);
}
int dep(int x){
    mkrt(rt);
    acc(x);splay(x); 
    return tr[x].siz;
}
int main(){
    cin>>n;
    for(int i = 1;i <= n;i ++){
        cin>>q[i][0];
        if(q[i][0] == 1)  cin>>q[i][1],a[++cnt] = q[i][1];
    }
    sort(a+1,a+cnt+1);
    cnt1 = unique(a+1,a+cnt+1) - a - 1;
    for(int i = 1;i <= n;i ++){
        if(q[i][0] == 1){
            q[i][1] = lower_bound(a+1,a+cnt1+1,q[i][1]) - a;        }
    }
    S.insert(INF);S.insert(-INF);
    for(int i = 1;i <= n;i ++){
        if(q[i][0] == 1){
            if(!cnt2){
                cnt2 ++;tr[cnt2].siz = 1;rt = q[i][1];S.insert(q[i][1]);
                printf("1\n");
                continue;
            }
            cnt2 ++;tr[cnt2].siz = 1;
            auto it = S.upper_bound(q[i][1]);
            int pr,su,mx=0,op;
            su=*it,--it,pr=*it;
            if(pr != -INF)  if(dep(pr) > mx)  mx = dep(pr),op = pr;
            if(su != INF)  if(dep(su) > mx)  mx = dep(su),op = su;
            printf("%d\n",mx+1);
            c[op][q[i][1] > op] = q[i][1],fa[q[i][1]] = op;
            link(op,q[i][1]);
            S.insert(q[i][1]);
        }
        if(q[i][0] == 2){
            if(cnt2 == 1){
                printf("1\n");continue;
            }
            auto it = S.begin();it++;
            int p = *it,y = c[p][1],z = fa[p],res = dep(p);
            if(p != rt){
                cut(p,z);cut(p,y);link(p,rt);link(z,y);
                fa[p] = 0,c[p][1] = rt,fa[rt] = p,rt = p,c[z][0] = y;fa[y] = z;
            }
            sdn<<res<<endl;
        }
        if(q[i][0] == 3){
            if(cnt2 == 1){
                printf("1\n");continue;
            }
            auto it = S.end();it--;it--;
            int p = *it,y = c[p][0],z = fa[p],res = dep(p);
            if(p != rt){
                cut(p,z),cut(p,y),link(p,rt),link(z,y);
                fa[p] = 0,c[p][0] = rt,fa[rt] = p,rt = p,c[z][1] = y;fa[y] = z;
            }
            sdn<<res<<endl;
        }
        if(q[i][0] == 4){
            if(cnt2 == 1){
                cnt2 = 0;S.erase(S.find(rt));rt = 0;
                printf("1\n");continue;
            }
            auto it = S.begin();it++;
            int p = *it,y = c[p][1],z = fa[p],res = dep(p);
            cut(p,z);cut(p,y);link(y,z);
            if(p == rt)  rt = y;
            c[p][0] = c[p][1] = fa[p] = 0,c[z][0] = y,fa[y] = z;
            cnt2 --;S.erase(S.find(p));
            sdn<<res<<endl;
        }
        if(q[i][0] == 5){
            if(cnt2 == 1){
                cnt2 = 0;S.erase(S.find(rt));rt = 0;
                printf("1\n");continue;
            }
            auto it = S.end();it--;it--;
            int p = *it,y = c[p][0],z = fa[p],res = dep(p);
            cut(p,z);cut(p,y);link(y,z);
            if(p == rt)  rt = y;
            c[p][0] = c[p][1] = fa[p] = 0,c[z][1] = y,fa[y] = z;
            cnt2 --;S.erase(S.find(p));
            sdn<<res<<endl;
        }
    }
    return 0;
}