传送门：https://loj.ac/problem/10145

简单的平衡树

————————————————————————————————————

1 #include
2 using namespace std;
3 const int maxn=1e5+10;
4 int n,minv,lk;
5 struct node
6 {
7 int val,lc,rc,siz,rd,delt;
8 }tr[maxn];
9 int cnt,root;
10 int newnode(int v)
11 {
12 tr[++cnt].val=v;
13 tr[cnt].lc=tr[cnt].rc=0;
14 tr[cnt].siz=1;
15 tr[cnt].rd=rand();
16 tr[cnt].delt=0;
17 return cnt;
18 }
19 void update(int cur)
20 {
21 tr[cur].siz=tr[tr[cur].lc].siz+tr[tr[cur].rc].siz+1;
22 }
23 void down(int cur)
24 {
25 if(!cur)return ;
26 if(tr[cur].delt)
27 {
28 tr[tr[cur].lc].val+=tr[cur].delt;
29 tr[tr[cur].rc].val+=tr[cur].delt;
30 tr[tr[cur].lc].delt+=tr[cur].delt;
31 tr[tr[cur].rc].delt+=tr[cur].delt;
32 tr[cur].delt=0;
33 }
34 }
35 int merge(int x,int y)
36 {
37 if(x*y==0)return x+y;
38 if(tr[x].rd=k)cur=tr[cur].lc;
123 else
124 {
125 k-=tr[tr[cur].lc].siz+1;
126 cur=tr[cur].rc;
127 }
128 }
129 }
130 void find(int v)
131 {
132 if(!root || tr[root].siz<v || v<=0)
133 {
134 puts("-1");
135 return ;
136 }
137 int x,y;
138 splitm(root,v-1,x,y);
139 printf("%d\n",kth(y,1));
140 root=merge(x,y);
141 }
142 int main()
143 {
144 scanf("%d%d",&n,&minv);
145 for(int x,i=0;i<n;++i)
146 {
147 scanf("%s%d",s,&x);
148 if(s[0]=='I')insert(x);
149 else if(s[0]=='A')add(x);
150 else if(s[0]=='S')add(-x);
151 else find(tr[root].siz-x+1);
152 }
153 printf("%d\n",lk);
154 return 0;
155 }