【bzoj3224】普通平衡树_di679520024669的博客-程序员秘密

看有没有人能发现咯。

#include<bits/stdc++.h>
#define N 300005
#define rat 4
#define pushup(o) if(o->lc->size)o->size=o->lc->size+o->rc->size,o->val=o->rc->val
#define newnode(s,v,a,b) (&(*st[cnt++]=Node(s,v,a,b)))
#define merge(a,b) newnode(a->size+b->size,b->val,a,b)
using namespace std;
struct Node{
    int size,val;Node *lc,*rc;
    Node(int s,int v,Node *a,Node *b):size(s),val(v),lc(a),rc(b){}
    Node(){}
}*rt,*nul;
struct Finger_Tree{
    Node *fa,t[N],*st[N];
    int cnt;
    inline void maintain(Node *o){
        if(o->lc->size>o->rc->size*4){
            o->rc=merge(o->lc->rc,o->rc);
            st[--cnt]=o->lc;o->lc=o->lc->lc;
        }
        else if(o->rc->size>o->lc->size*4){
             o->lc=merge(o->lc,o->rc->lc);
             st[--cnt]=o->rc;o->rc=o->rc->rc;
        }
    }
    int find(int x,Node *o){
        if(o->size==1)return o->val;
        return x>o->lc->size?find(x-o->lc->size,o->rc):find(x,o->lc);
    }
    int queryrank(int x,Node *o){
        if(o->size==1)return 1;
        return x>o->lc->val?queryrank(x,o->rc)+o->lc->size:queryrank(x,o->lc);
    }
    void ins(int x,Node *o){
        if(o->size==1){
            o->lc=newnode(1,min(x,o->val),nul,nul);
            o->rc=newnode(1,max(x,o->val),nul,nul);
        }
        else ins(x,x>o->lc->val?o->rc:o->lc);
        pushup(o);maintain(o);
    }
    void del(int x,Node *o){
        if(o->size==1)*fa=o==fa->lc?*fa->rc:*fa->lc;
        else fa=o,del(x,x>o->lc->val?o->rc:o->lc);
        pushup(o);maintain(o);
    }
}T;
inline int read(){
    register int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int main(){
    int n=read();
    for(int i=0;i<=N-5;i++)T.st[i]=&T.t[i];
    nul=new Node(0,0,0,0);
    rt=new Node(1,2147483647,nul,nul);
    while(n--){
        int opt=read(),x=read();
        if(opt==1)T.ins(x,rt);
        if(opt==2)T.del(x,rt);
        if(opt==3)printf("%d\n",T.queryrank(x,rt));
        if(opt==4)printf("%d\n",T.find(x,rt));
        if(opt==5)printf("%d\n",T.find(T.queryrank(x,rt)-1,rt));
        if(opt==6)printf("%d\n",T.find(T.queryrank(x+1,rt),rt));
    }
    return 0;
}