当 opt=4 的时候，这一个卡点，卡了我一个多小时，给孩子调疯了，我看了看俩 AC 记录，全不是线段树，孩子只好孤军奋战了。
孩子的方法比较玄学，操作4的复杂度大概是 ，基于倍增实现的，基于二分的话可能会快一些，另外三个操作均为 .卡了很长时间才想到可以二分，然后写了半天才发现自己离散化又出问题了，改了改离散化，去了去重，才勉勉强强 AC 掉，孩子快累死了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
class edge
{
public:
int l,r,x;
}tree[maxn];
int n;
void build(int p,int l,int r)
{
tree[p].l=l,tree[p].r=r;
if(l==r)
return;
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
return;
}
void change(int p,int l,int r,int k)
{
if(l<=tree[p].l && tree[p].r<=r)
{
tree[p].x+=k;
return;
}
int mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid)
change(p*2,l,r,k);
if(r>=mid+1)
change(p*2+1,l,r,k);
tree[p].x=tree[p*2].x+tree[p*2+1].x;
return;
}
int check(int p,int l,int r)
{
if(l<=tree[p].l && tree[p].r<=r)
{
return tree[p].x;
}
int mid=(tree[p].l+tree[p].r)>>1;
int ans=0;
if(l<=mid)
ans+=check(p*2,l,r);
if(r>=mid+1)
ans+=check(p*2+1,l,r);
return ans;
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
typedef pair<int,int> longhao;
longhao m[maxn];
int san[maxn];//first -> x, second -> opt
int max1;
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
m[i].second=read(),m[i].first=read();
if(m[i].second==1)
san[++san[0]]=m[i].first;
}
sort(san+1,san+1+san[0]);
int k=unique(san+1,san+1+san[0])-(san+1);
build(1,1,k);
for(int i=1;i<=n;i++)
{
int x=lower_bound(san+1,san+1+k,m[i].first)-san;
int opt=m[i].second;
if(opt==1)
change(1,x,x,1);
else if(opt==2)
change(1,x,x,-1);
else if(opt==3)
printf("%d\n",check(1,1,x-1)+1);
else if(opt==4)
{
int sum=0,p=1;
x=m[i].first;
while(p!=0)
{
if(check(1,1,sum+p)<x)
sum+=p,p*=2;
else
p/=2;
}
printf("%d\n",san[sum+1]);
}
}
return 0;
}
Update 十几分钟后：眼瞎了，wyf 用的就是线段树