https://www.luogu.org/problemnew/show/P3369
知识点：1.拆分split,合并merge
2.split,merge要点：通过传址调用来简便代码
3.记得root = merge(xxxxx,xxxxx);
2 wrong in code
#include <bits/stdc++.h>
#define M 200002
using namespace std;
int tot = ;
int val[M],rd[M];
int ch[M][];
int root = ;
int m;
int siz[M];
int newnode(int x)
{
siz[++tot] = ;
val[tot] = x;
rd[tot] = rand();
return tot;
}
void updata(int x)
{
siz[x] = siz[ch[x][]] + siz[ch[x][]] + ;
}
void split(int now,int k,int &x,int &y)
{
if(!now)
{
x = y = ;
return;
}
else
{
if(val[now] <= k)
{
x = now;
split(ch[now][],k,ch[now][],y);
}
else
{
y = now;
split(ch[now][],k,x,ch[now][]);
}
updata(now);
}
}
int merge(int A,int B)
{
if(!A || !B) return A + B;
if(rd[A] < rd[B]){ch[A][] = merge(ch[A][],B); updata(A); return A;}
else {ch[B][] = merge(A,ch[B][]); updata(B); return B;}
}
void insert(int t)
{
int x,y;
split(root,t,x,y);
root = merge(merge(x,newnode(t)),y);
}
void del(int t)
{
int x,y,z;
split(root,t,x,z);
split(x,t - ,x,y);//wrong 1:是 split(x,t - 1,x,y)而不是 split(root,t - 1,x,y)
y = merge(ch[y][],ch[y][]);//wrong 2: 记得y =
root = merge(merge(x,y),z);
}
int findrk(int t)
{
int x,y;
split(root,t - ,x,y);
int ans = siz[x] + ;
root = merge(x,y);
return ans;
}
int kth(int now,int k)
{
while(now)
{
if(k <= siz[ch[now][]]) now = ch[now][];
else if(k == siz[ch[now][]] + ) return now;
else k -= siz[ch[now][]] + ,now = ch[now][];
}
return now;
}
int front(int k)
{
int x,y;
split(root,k - ,x,y);
int ans = val[kth(x,siz[x])];
root = merge(x,y);
return ans;
}
int back(int k)
{
int x,y;
split(root,k,x,y);
int ans = val[kth(y,)];
root = merge(x,y);
return ans;
}
int main()
{
srand();
scanf("%d",&m);
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
if(x == )
{
insert(y);
}
if(x == )
{
del(y);
}
if(x == )
{
printf("%d\n",findrk(y));
}
if(x == )
{
printf("%d\n",val[kth(root,y)]);
}
if(x == )
{
printf("%d\n",front(y));
}
if(x == )
{
printf("%d\n",back(y));
}
}
return ;
}