RT,倒数第二个点WA(负数)
code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int ml=1,mr=1e7,maxn=1001010,it=0x3f3f3f3f;
int cnt=1,tree[maxn*4],tls[maxn*4],trs[maxn*4];
void spread(int p){
if(!tls[p]){
tls[p]=++cnt;
}
if(!trs[p]){
trs[p]=++cnt;
}
}
void add(int x,int d,int p=1,int cl=ml,int cr=mr){
if(cl==cr){
tree[p]+=d;
return;
}
int mid=(cr+cl-1)/2;
spread(p);
if(x<=mid){
add(x,d,tls[p],cl,mid);
}
else{
add(x,d,trs[p],mid+1,cr);
}
tree[p]=tree[tls[p]]+tree[trs[p]];
}
int ask(int l,int r,int p=1,int cl=ml,int cr=mr){
if(cl>r||cr<l)return 0;
if(cl>=l&&cr<=r){
return tree[p];
}
int mid=(cl+cr-1)/2;
spread(p);
return ask(l,r,tls[p],cl,mid)+ask(l,r,trs[p],mid+1,cr);
}
void insert(int v){
add(v,1);
}
void remov(int v){
add(v,-1);
}
int countl(int v){
return ask(ml,v-1);
}
int countg(int v){
return ask(v+1,mr);
}
int rnk(int v){
return countl(v)+1;
}
int kth(int k,int p=1,int cl=ml,int cr=mr){
if(cl==cr)return cl;
int mid=(cl+cr-1)/2;
if(tree[tls[p]]>=k)return kth(k,tls[p],cl,mid);
else return kth(k-tree[tls[p]],trs[p],mid+1,cr);
}
int pre(int v){
int r=countl(v);
return kth(r);
}
int suc(int v){
int r=tree[1]-countg(v)+1;
return kth(r);
}
signed main(){
ios::sync_with_stdio(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
int opt,v;
cin>>opt>>v;
switch(opt){
case 1:
insert(v);
break;
case 2:
remov(v);
break;
case 3:
cout<<rnk(v)<<'\n';
break;
case 4:
cout<<kth(v)<<'\n';
break;
case 5:
cout<<pre(v)<<'\n';
break;
case 6:
cout<<suc(v)<<'\n';
break;
}
}
}