权值线段树求条

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Node{
    int l,r;
    long long sum;
}t[N<<2];
int n;
int a[N],op[N],k[N];
map <int,int> mp;
int cnt=1;
void pushup(int i){
    t[i].sum=t[i<<1].sum+t[i<<1|1].sum;
}
void build(int i,int l,int r){
    t[i].l=l;
    t[i].r=r;
    if(l==r){
        t[i].sum=0;
        return;
    }
    int mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    pushup(i);
}
void change(int i,int pos,long long x){
    if(t[i].l>pos||t[i].r<pos)
        return;
    if(t[i].l==t[i].r&&t[i].l==pos){
        t[i].sum+=x;
        return;
    }
    change(i<<1,pos,x);
    change(i<<1|1,pos,x);
    pushup(i);
}
long long query1(int i,int l,int r){
    if(a[t[i].l]>r||a[t[i].r]<l)
        return 0;
    if(a[t[i].l]>=l&&a[t[i].r]<=r)
        return t[i].sum;
    return query1(i<<1,l,r)+query1(i<<1|1,l,r);
}
long long query2(int i,int x){
    if(t[i].l==t[i].r)
        return t[i].l;
    if(x<=t[i<<1].sum)
        return query2(i<<1,x);
    else
        return query2(i<<1|1,x-t[i<<1].sum);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>op[i]>>k[i];
        if(op[i]==1)
            a[cnt++]=k[i];
    }
    cnt--;
    sort(a+1,a+1+cnt);
    int* ed=unique(a+1,a+1+cnt);
    cnt=ed-(a+1);
    for(int i=1;i<=cnt;i++)
        mp[a[i]]=i;
    build(1,1,cnt);
    for(int i=1;i<=n;i++){
        if(op[i]==1)
            change(1,mp[k[i]],1);
        else if(op[i]==2)
            change(1,mp[k[i]],-1);
        else if(op[i]==3)
            cout<<query1(1,a[1],k[i]-1)+1<<endl;
        else if(op[i]==4)
            cout<<a[query2(1,k[i])]<<endl;
        else if(op[i]==5){
            int x=query1(1,a[1],k[i]),y=query1(1,a[x],a[x]);
            //cout<<x<<endl;
            if(a[x]==k[i])
                cout<<a[query2(1,x-y)]<<endl;
            else
                cout<<a[query2(1,x)]<<endl;
        }

        else{
            int x=query1(1,a[1],k[i]),y=query1(1,a[x],a[x]);
            if(a[x]==k[i])
                cout<<a[query2(1,x+y+1)]<<endl;
            else
                cout<<a[query2(1,x+1)]<<endl;
        }

    }
    return 0;
}