发现这个题可以用权值线段树做,就写了一个,结果挂了
#include<bits/stdc++.h>
#define int long long
#define ls t[rt].lson
#define rs t[rt].rson
using namespace std;
struct node{
int l,r,lson,rson,sum;
}t[5000005];
int idx;
void build(){
idx=1;
t[1].l=-1e7,t[1].r=1e7;
}
void pushup(int rt){
t[rt].sum=t[ls].sum+t[rs].sum;
}
void add(int rt,int k){
if (t[rt].l>k||t[rt].r<k)return;
if (t[rt].l==k&&t[rt].r==k){
t[rt].sum++;
return;
}
if (!ls){
ls=++idx;
int mid=floor((double)(t[rt].l+t[rt].r)/2.0);
t[ls].l=t[rt].l;
t[ls].r=mid;
rs=++idx;
t[rs].l=mid+1;
t[rs].r=t[rt].r;
}
add(ls,k);
add(rs,k);
pushup(rt);
}
void del(int rt,int k){
if (t[rt].l>k||t[rt].r<k)return;
if (t[rt].l==k&&t[rt].r==k){
t[rt].sum--;
return;
}
if (!ls){
return;
}
del(ls,k);
del(rs,k);
pushup(rt);
}
int query(int rt,int l,int r){
if (t[rt].l>r||t[rt].r<l)return 0;
if (t[rt].l>=l&&t[rt].r<=r){
return t[rt].sum;
}
if (!ls){
return 0;
}
return query(ls,l,r)+query(rs,l,r);
}
int grank(int rt,int k){
if (t[rt].sum<k)return -1;
if (t[rt].l==t[rt].r)return t[rt].l;
if (t[ls].sum>=k)return grank(ls,k);
else return grank(rs,k-t[ls].sum);
}
int qq(int k){
int t=query(1,-1e7,k-1);
return grank(1,t);
}
int hj(int k){
int t=query(1,-1e7,k);
return grank(1,t+1);
}
signed main(){
int n;
cin>>n;
build();
for (int i=1;i<=n;i++){
int op,x;
cin>>op>>x;
switch(op){
case 1:
add(1,x);
break;
case 2:
add(2,x);
break;
case 3:
cout<<query(1,-1e7,x-1)+1<<endl;
break;
case 4:
cout<<grank(1,x)<<endl;
break;
case 5:
cout<<qq(x)<<endl;
break;
case 6:
cout<<hj(x)<<endl;
}
}
return 0;
}