关于count的计算有问题,不知道怎么改
#include<bits/stdc++.h>
using namespace std;
int n;
struct Node{
int key;
int val;
int count;
int lc,rc;
}tree[800000+1];
int sign=0;
int root=0;
mt19937 rander(100000);
void PushUp(int k){
tree[k].count=1;
if(tree[k].lc)tree[k].count+=tree[tree[k].lc].count;
if(tree[k].rc)tree[k].count+=tree[tree[k].rc].count;
}
pair<int,int>Split(int k,int val){//按val切割以k为根的树,返回两棵树
//cout<<'s'<<'\n';
if(!k)return make_pair(0,0);
else if(tree[k].val<=val){
pair<int,int>p=Split(tree[k].rc,val);
tree[k].rc=p.first;
PushUp(k);
return make_pair(k,p.second);
}else{
pair<int,int>p=Split(tree[k].lc,val);
tree[k].lc=p.second;
PushUp(k);
return make_pair(p.first,k);
}
}
int Merge(int k1,int k2){
//cout<<'m'<<'\n';
if((!k1)||(!k2))return k1+k2;
else if(tree[k1].key<tree[k2].key){
tree[k1].rc=Merge(tree[k1].rc,k2);
PushUp(k1);
return k1;
}else{
tree[k2].lc=Merge(k1,tree[k2].lc);
PushUp(k2);
return k2;
}
}
void Insert(int val){
if(!root){
root=++sign;
tree[root].count=1;
tree[root].val=val;
tree[root].key=rander();
return;
}
pair<int,int>p=Split(root,val);
++sign;
tree[root].count=1;
tree[sign].val=val;
tree[sign].key=rander();
root=Merge(p.first,Merge(sign,p.second));
}
void Delete(int val){
pair<int,int>p1=Split(root,val);
pair<int,int>p2=Split(p1.first,val-1);
int newR=Merge(tree[p2.second].lc,tree[p2.second].rc);
root=Merge(Merge(p2.first,newR),p1.second);
}
int Rank(int val){
pair<int,int>p=Split(root,val-1);
int ret=tree[p.first].count+1;
root=Merge(p.first,p.second);
return ret;
}
int At(int rank){
int now=root;
while(true){
if(rank<=tree[tree[now].lc].count)now=tree[now].lc;
else if(rank==tree[tree[now].lc].count+1){
return tree[now].val;
}else{
rank-=tree[tree[now].lc].count+1;
now=tree[now].rc;
}
}
}
int Pre(int x){
pair<int,int>p=Split(root,x-1);
int ans,now=p.first;
while(true){
//cerr<<tree[now].val<<'p';
if(tree[now].rc)now=tree[now].rc;
else{
ans=tree[now].val;
break;
}
}
//cerr<<endl;
root=Merge(p.first,p.second);
return ans;
}
int Suc(int x){
pair<int,int>p=Split(root,x);
int ans,now=p.second;
while(true){
if(tree[now].lc)now=tree[now].lc;
else{
ans=tree[now].val;
break;
}
}
root=Merge(p.first,p.second);
return ans;
}
void Solve(){
cin>>n;
for(int i=1;i<=n;i++){
int op,x;
cin>>op>>x;
if(op==1){
Insert(x);
}else if(op==2){
Delete(x);
}else if(op==3){
cout<<Rank(x)<<'\n';
}else if(op==4){
cout<<At(x)<<'\n';
}else if(op==5){
cout<<Pre(x)<<'\n';
}else if(op==6){
cout<<Suc(x)<<'\n';
}
for(int i=1;i<=8;i++)cout<<'-';
cout<<'\n';
cout<<root;
cout<<'\n';
for(int i=1;i<=sign;i++)
cout<<tree[i].val<<' '
<<tree[i].key<<' '
<<tree[i].count<<' '
<<tree[i].lc<<' '
<<tree[i].rc<<'\n';
for(int i=1;i<=8;i++)cout<<'-';
cout<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
Solve();
return 0;
}