44pts求条
查看原帖
44pts求条
1243510
bgbwgxy楼主2025/6/17 18:50
//
// Created by ?w ? on 25-6-11.
//
#include <bits/stdc++.h>
using namespace std;
const int maxsize=100001;
int lef[maxsize];
int righ[maxsize];
int head=0;
int val[maxsize];
// int count [maxsize];
int deep[maxsize];
int root[maxsize];
int cnt =0;
// const int inf = 10000001;
int keycount [maxsize];
int siz[maxsize];
void  up(int i ) {
    siz [i]=siz[lef[i]]+siz[righ[i]]+keycount[i];
    deep[i]=max(deep[lef[i]],deep[righ[i]])+1;
}
int  leftdown(int i ) {
    int r=righ[i];
    // int l=lef[lef[i]];

    righ[i]=lef[r ];
    lef[r]=i;
    up(i);
    up(r);
    return r;
}
int rightdown(int i ) {
    int l=lef[i];
    // int r=righ[righ[i]];

    lef[i]=righ[l];
    righ[l]=i;
    up(i);
    up(l);
    return l;
}
int  maintain(int i ) {
    int x= deep[lef[i]];
    int y =deep[righ[i]];
    if ((x-y)>1) {
        if (deep[lef[lef[i]]]>=deep[righ[lef[i]]]) {
            i=rightdown(i);
        }
        else {
            lef[i]=leftdown(lef[i]);
            i=rightdown(i);
        }
    }
    if ((y-x)>1 ) {
        if (deep[righ[righ[i]]]>=deep[lef[righ[i]]]) {
            i=leftdown(i);
        }
        else {
            righ[i]=rightdown(righ[i]);
            i=leftdown(i);
        }
    }return i;
}
int  insert(int x ,int i) {
    if (!i) {
        val[++cnt]=x;
        keycount[cnt]=siz[cnt]=deep[cnt]=1;
        return cnt;
        // up(i);
        // return maintain(i);
    }
    if (val[i]==x  ) {
        // val[i]=x;
        // siz[i]++;
        keycount[i]++;
    }else {
        if (val[i]>x ) {
            lef[i]=insert(x ,lef[i]);
        }else {
            righ[i]=insert(x ,righ[i]);
        }

    }
    up(i);
    return maintain(i);
}
int delleft(int i ,int r) {
    if (r==i) {
        return righ[i];
    }
    lef[i]=delleft(lef[i],r);
    up(i);
    return maintain(i);
}
int  del(int x ,int i) {
    if (val[i]==x ) {
        if (keycount[i]>1) {
            keycount[i]--;
            // return i ;
        }
        else {
            // keycount[i]=0;
            if (lef[i]==righ[i]==0) {
                return 0;
            }else {
                if (lef [i]==0) {
                    i=righ[i];

                }
                else {
                    if (righ[i]==0) {
                        i=lef[i];
                    }



                    else {
                        int cur =righ[i];
                        while (lef[cur ]) {
                            cur = lef[cur];
                        }
                        righ[i]=delleft(righ[i],cur);
                        lef[cur ]=lef[i];
                        righ[cur ]=righ[i];
                        i=cur ;
                    }
                }
            }
        }
    }else {
        if (val[i]>x ) {
            lef[i]=del(x ,lef[i]);
        }
        if (val[i]<x ) {
            righ[i]=del(x ,righ[i]);
        }
    }
    up(i);
    return maintain(i);
}


    // if (val[i]<x ) {
    //     i=del(x ,righ[i]);
    // }
    // else {
    //     i=del(x,lef[i]);
    // }
    // up(i);
    // return maintain(i);
int query_cnt (int x,int i) {
    // if (siz[lef[i]]<=x) {
    //     if (keycount[i]+siz[lef[i]]>=x) {
    //         return val[i];
    //     }
    //     // return query_cnt(x-siz[lef[i]]-keycount[i],lef[i]);
    // }
    if (siz[lef[i]]>=x) {
        return query_cnt(x ,lef[i]);
    }else {
        if (siz[lef[i]]+keycount[i]<x) {
            return query_cnt(x-siz[lef[i]]-keycount[i],righ[i]);
        }
    }
    return val[i];
}
int query_sum(int x,int i) {
    if (!i)
        return 0;
    if (val[i]>=x ) {
        return query_sum(x ,lef[i]);
    }
    return keycount[i]+siz[lef[i]]+query_sum(x ,righ[i]);
}
int query_pre(int x,int i ) {
    if (!i)
        return INT_MIN;
    if (val[i] >= x) {
        return query_pre(x ,lef[i]);
    }
    return max(val[i],query_pre(x ,righ[i]));
}
int query_next(int x,int i) {
    if (!i)
        return INT_MAX;
    if (val[i]<=x) {
        return query_next(x ,righ[i]);
    }
    return min(val[i],query_next(x ,lef[i]));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,a,b;
    cin>>n;
    for (int i=0;i<n;i++) {
        cin>>a>>b;
        if (a==1) {
            head=insert(b,head);
        }
        if (a==2) {
            head=del(b,head);
        }
        if (a==3) {
            cout<<query_sum(b,head)+1<<'\n';
        }
        if (a==4) {
            cout<<query_cnt(b,head)<<'\n';
        }

        if (a==5) {
            cout<<query_pre(b,head)<<'\n';
        }
        if (a==6) {
            cout<<query_next(b,head)<<'\n';
        }
    }
    memset(keycount + 1, 0, cnt * sizeof(int));
    memset(deep + 1, 0, cnt * sizeof(int));
    memset(lef + 1, 0, cnt * sizeof(int));
    memset(righ + 1, 0, cnt * sizeof(int));
    memset(val + 1, 0, cnt * sizeof(int));
    memset(siz + 1, 0, cnt * sizeof(int));
    cnt = 0;
    head = 0;

}
2025/6/17 18:50
加载中...