参考了:
https://www.luogu.com.cn/discuss/514163
感觉可能是类似的问题,按照上贴检查了一下就20->60
求调:
//Author: Velvet on Luogu(uid=443675)
#include <bits/stdc++.h>
#define mkpr make_pair
#define fi first
#define se second
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(int x){write(x);putchar('\n');}
inline void writesp(int x){write(x);putchar(' ');}
inline int lowbit(int x) {return x&(-x);}
typedef pair<int,int> Pair;
const int N=100005;
struct Tree{int l,r,val,siz,rnd;} a[N];
int n,tot,root,x,y,z;
inline void pushup(int p){a[p].siz=a[a[p].l].siz+a[a[p].r].siz+1;}
void split(int p,int k,int &x,int &y){
if(!p){x=y=0;return ;}
if(a[p].val<=k) {x=p;split(a[p].r,k,a[p].r,y);}
else {y=p;split(a[p].l,k,x,a[p].l);}
pushup(p);
}
int merge(int u,int v){
if(!u||!v) return u|v;
if(a[u].rnd<a[v].rnd){
a[u].r=merge(a[u].r,v);
pushup(u);return u;
}else{
a[v].l=merge(u,a[v].l);
pushup(v);return v;
}
}
int New(int v){
a[++tot].val=v;a[tot].siz=1,a[tot].rnd=rand();
return tot;
}
void Insert(int v){
split(root,v,x,y);
root=merge(merge(x,New(v)),y);
}
void Delete(int v){
split(root,v,x,y);split(x,v-1,x,z);
z=merge(a[z].l,a[z].r);
root=merge(merge(x,y),z);
}
int Qkth(int p,int k){
while(1){
if(k<=a[a[p].l].siz) p=a[p].l;
else if(k==a[a[p].l].siz+1) return p;
else k=k-a[a[p].l].siz-1,p=a[p].r;
}
}
int Qfront(int v){
split(root,v-1,x,y);
int rt=a[Qkth(x,a[x].siz)].val;
root=merge(x,y);
return rt;
}
int Qnxt(int v){
split(root,v,x,y);
int rt=a[Qkth(y,1)].val;
root=merge(x,y);
return rt;
}
int Qrank(int v){
split(root,v-1,x,y);
int rt=a[x].siz+1;
root=merge(merge(x,y),z);
return rt;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;srand(time(0));
while(n--){
int op,v;cin>>op>>v;
if(op==1) Insert(v);
else if(op==2) Delete(v);
else if(op==3) cout<<Qrank(v)<<'\n';
else if(op==4) cout<<a[Qkth(root,v)].val<<'\n';
else if(op==5) cout<<Qfront(v)<<'\n';
else cout<<Qnxt(v)<<'\n';
}
return 0;
}