insert函数有时输出会多1

#include <bits/stdc++.h>
using namespace std;
struct tree{
	int l,r,sum;
}at[400005];
int n,opt[100005],a[100005],push[100005],push1[100005],quan[100005],ls[100005],hy[100005],place[100005],totpush;
void build(int root,int x,int y){
	if(x==y){
		at[root].l=x;
		at[root].r=y;
		return ;
	}
	at[root].l=x;
	at[root].r=y;
	at[root].sum=0;
	int mid=(x+y)/2;
	build(root*2,x,mid);build(root*2+1,mid+1,y);
}
void insert(int root, int va, int der){ 
    if(at[root].l == at[root].r){ 
        at[root].sum += der;
        return ;
    }
    int mid = (at[root].l + at[root].r) / 2; 
    if(va <= mid){
        insert(root * 2, va, der);  
    } else {
        insert(root * 2 + 1, va, der);  
    }
    at[root].sum = at[root * 2].sum + at[root * 2 + 1].sum;
}
int search(int root,int x,int y){
	if (x > y) return 0;
	if(at[root].l>=x && at[root].r<=y) return at[root].sum;
	if(at[root].l>y||at[root].r<x) return 0;
	int mid=(at[root].l+at[root].r)/2,tt=0;
	if(x<=mid) tt+=search(root*2,x,mid);
	if(y>mid){
		tt+=search(root*2+1,mid+1,y);
	}
	return tt;
}
int pm(int root,int x){
	if(at[root].l==at[root].r) return at[root].l;
	if(at[root*2].sum>=x) return pm(root*2,x);
	else return pm(root*2+1,x-at[root*2].sum);
}
int cc(int root,int x){
	if(at[root].r <= x){
        return at[root].sum;
    }
    if(at[root].l > x){
        return 0; 
    }
    
    int mid = (at[root].l + at[root].r) / 2;
    int cnt = cc(root * 2, x); 
    if(x > mid){
        cnt += cc(root * 2 + 1, x);  
    }
    return cnt;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>opt[i]>>a[i];
		if(opt[i]!=4){
			push[++totpush]=a[i];
			push1[totpush]=a[i];
			place[totpush]=i;
		} 
	}
	sort(push+1,push+totpush+1);
	int num=unique(push+1,push+totpush+1)-push-1;
	int maxx=-1;
	for(int i=1;i<=totpush;i++){
		int p=lower_bound(push+1,push+num+1,push1[i])-push;
		ls[place[i]]=p;
		if(p>maxx) maxx=p;
		hy[p]=push1[i];
	}
	build(1,1,maxx);
	for(int i=1;i<=n;i++){
		if(opt[i]==1){
			insert(1,ls[i],1);
		}
		if(opt[i]==2){
			insert(1,ls[i],-1);
		}
		if(opt[i]==3){
			cout<<search(1,1,ls[i]-1)+1<<endl;
		}
		if(opt[i]==4){
			cout<<hy[pm(1,a[i])]<<endl;
		}
		if(opt[i]==5){
			cout<<hy[pm(1,cc(1,ls[i]-1))]<<endl;
		}
		if(opt[i]==6){
			cout<<hy[pm(1,cc(1,ls[i])+1)]<<endl;
		}
	}
	return 0;
}

评测记录