很奇怪,有时候不会爆,有时候会爆,有时候能做到一半才会爆
#include<bits/stdc++.h>
using namespace std;
const int M=1e7+10;
int cnt,root;
struct Node{
int ls,rs;
int key,pri;
int siz;
}t[M];
void update(int x)
{
t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;
}
void newnode(int x)
{
cnt++;
t[cnt].key=x;
t[cnt].siz=1;
t[cnt].pri=rand();
}
void Split(int rt,int x,int &L,int &R)
{
if(rt==0) {L=R=0;return;}
if(x>=t[rt].key){
L=rt;
Split(t[rt].rs,x,t[rt].rs,R);
}
else{
R=rt;
Split(t[rt].ls,x,L,t[rt].ls);
}
update(rt);
}
int Merge(int &L,int &R)
{
if(L==0||R==0) return L+R;
if(t[L].pri>t[R].pri){
t[L].rs=Merge(t[L].rs,R);
update(L);
return L;
}
else{
t[R].ls=Merge(L,t[R].ls);
update(R);
return R;
}
}
void Insert(int x){
int L,R;
Split(root,x,L,R);
newnode(x);
int aa=Merge(L,cnt);
root=Merge(aa,R);
}
void Del(int x){
int L,R,p;
Split(root,x,L,R);//L,R:<=x的子树,>x的子树
Split(root,x-1,L,p);//L,p:<=x-1的子树,就是<x的子树,>x-1的子树,就是>=x的子树
//又因为前面一行将根、左子树与右子树剥离,所以这里>=x就是==x
p=Merge(t[p].ls,t[p].rs);//将==x为根的左右子树合并,p点就相当于被删除了,p‘点此时更新为左右子树根节点优先级高的那一个
int aa=Merge(L,p);//中间量aa:合并<x的子树与原p点,现p’点的子树
root=Merge(aa,R);
}
void Rank(int x){
int L,R;
Split(root,x-1,L,R);//同del函数
printf("%d\n",t[L].siz+1);
root=Merge(L,R);
}
int kth(int rt,int k)
{
int siz=t[t[rt].ls].siz;
if(siz+1==k) return rt;
if(siz>=k) return kth(t[rt].ls,k);
return kth(t[rt].rs,k-siz-1);
}
void Precursor(int x)
{
int L,R;
Split(root,x-1,L,R);
printf("%d\n",t[kth(L,t[L].siz)].key);
root=Merge(L,R);
}
void Successor(int x)
{
int L,R;
Split(root,x,L,R);
printf("%d\n",t[kth(R,1)].key);
root=Merge(L,R);
}
int main(){
//freopen("3369.in","r",stdin);
//freopen("3369.out","w",stdout);
srand(time(NULL));
int n;
cin>>n;
while(n--){
int opt,x;
scanf("%d%d",&opt,&x);
switch(opt){
case 1:Insert(x);break;//加点
case 2:Del(x);break;//删点
case 3:Rank(x);break;//查询比 x 小的个数,并且将得到的答案加一
case 4:printf("%d\n",t[kth(root,x)].key);break;//询问排名为x的权值
case 5:Precursor(x);break;//前驱
case 6:Successor(x);break;//后驱
}
}
return 0;
}