rt。
似乎是查询一个不在集合里的数的排名时挂了?有没有大佬教教我咋改
#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;
const int N=1e5+10; int root,tot,ans,v[N],w[N],c[N],s[N],lc[N],rc[N];
int new_node(int _v) { return v[++tot]=_v,w[tot]=rand(),c[tot]=s[tot]=1,tot; }
void update(int k) { s[k]=s[lc[k]]+s[rc[k]]+c[k]; }
void lturn(int &k) {
int t=rc[k];
rc[k]=lc[t],lc[t]=k,s[t]=s[k];
update(k),k=t;
}
void rturn(int &k) {
int t=lc[k];
lc[k]=rc[t],rc[t]=k,s[t]=s[k];
update(k),k=t;
}
void insert(int &k,int x) {
if(!k) return k=new_node(x),void();
s[k]++;
if(v[k]==x) c[k]++;
else if(v[k]<x) {
insert(rc[k],x);
if(w[rc[k]]<w[k]) lturn(k);
}
else {
insert(lc[k],x);
if(w[lc[k]]<w[k]) rturn(k);
}
}
bool del(int &k,int x) {
if(!k) return false;
if(v[k]==x) {
if(c[k]>1) return c[k]--,s[k]--,true;
else if(!lc[k]||!rc[k]) return k=lc[k]+rc[k],true;
else {
if(w[lc[k]]<w[rc[k]]) rturn(k);
else lturn(k);
return del(k,x);
}
}
else {
bool flag;
if(v[k]<x) flag=del(rc[k],x);
else flag=del(lc[k],x);
if(flag) s[k]--;
return flag;
}
}
int query_rank(int k,int x) {
if(!k) return 0;
if(v[k]==x) return s[lc[k]]+1;
if(x<v[k]) return query_rank(lc[k],x);
return s[lc[k]]+c[k]+query_rank(rc[k],x);
}
int query_kth(int k,int x) {
if(!k) return 0;
if(x<=s[lc[k]]) return query_kth(lc[k],x);
if(x>s[lc[k]]+c[k]) return query_kth(rc[k],x-s[lc[k]]-c[k]);
return v[k];
}
void query_pre(int k,int x) {
if(!k) return;
if(v[k]<x) ans=k,query_pre(rc[k],x);
else query_pre(lc[k],x);
}
void query_suc(int k,int x) {
if(!k) return;
if(v[k]>x) ans=k,query_suc(lc[k],x);
else query_suc(rc[k],x);
}
int main() {
srand(time(0));
int n; scanf("%d",&n);
while(n--) {
int opt,x; scanf("%d %d",&opt,&x);
if(opt==1) insert(root,x);
if(opt==2) del(root,x);
if(opt==3) printf("%d\n",query_rank(root,x));
if(opt==4) printf("%d\n",query_kth(root,x));
if(opt==5) query_pre(root,x),printf("%d\n",v[ans]);
if(opt==6) query_suc(root,x),printf("%d\n",v[ans]);
}
return 0;
}