```
#include<bits/stdc++.h>
using namespace std;
#define rep(i,k,n) for(long long i=k;i<=n;i++)
#define per(i,n,k) for(long long i=n;i>=k;i--)
#define pb push_back
#define fi first
#define se second
///#pragma GCC optimize(3,"Ofast","inline")
typedef unsigned long long ull;
//#define ll __int128
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<ll,ll> pll;
inline ll gcd(ll a,ll b)
{
while(b^=a^=b^=a%=b);
return a;
}
inline void write(ll x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
}
inline ll read()
{
ll x=0;
char f=1,c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
inline ll fmul(ll a,ll b,ll mod)
{
ll ans=0;
a%=mod;
while(b)
{
if(b&1LL)
ans=(ans+a)%mod;
a=(a+a)%mod;
b>>=1LL;
}
return ans;
}
inline ll fp(ll a,ll b,ll mod)
{
ll ans=1LL;
a%=mod;
while(b)
{
if(b&1LL)
ans=ans*a%mod;
a=a*a%mod;
b>>=1LL;
}
return ans;
}
inline ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
const int maxn=1e5+1;
int tree[maxn<<3];
int x[maxn],op[maxn],lsh[maxn],id[maxn],num[maxn];
void Update(int p,int v,int rt,int l,int r)///分别代表插入的数字，加还是减，访问的节点以及节点范围
{
tree[rt]+=v;
if(l==r)return;
int mid=l+r>>1;///区间中值
if(p<=mid)Update(p,v,rt<<1,l,mid);
else Update(p,v,rt<<1|1,mid+1,r);
}
int Rank(int x,int rt,int l,int r)///根本不需要到l==r的时候
{
if(x>r)return tree[rt];
int mid=l+r>>1;
int ans=0;
if(x>mid)ans+=Rank(x,rt<<1|1,mid+1,r);
else ans+=Rank(x,rt<<1,l,mid);
return ans;
}
int Kth(int x,int rt,int l,int r)///查询排名为k的数字
{
if(l==r)return l;
int mid=l+r>>1;
if(x>tree[rt<<1])return Kth(x-tree[rt<<1],rt<<1|1,mid+1,r);///如果x大于左节点的数量，那么只能去右节点找剩下x-tree[rt<<1]的数字
else return Kth(x,rt<<1,l,mid);
}
int Findpre(int rt,int l,int r)///确定区间以后就来找最大值
{
if(l==r)return l;
int mid=l+r>>1;
if(tree[rt<<1|1])///去有值的节点找
return Findpre(rt<<1|1,mid+1,r);
return Findpre(rt<<1,l,mid);
}
int Pre(int x,int rt,int l,int r)///用来确定前驱在哪个区间里面
{
if(r<x)///如果区间最大值小于x，那么可以在这个区间里面找最大值
{
if(tree[rt])return Findpre(rt,l,r);
return 0;///如果这个区间没有值，那么直接返回就行
}
int mid=l+r>>1;///跟区间中值比一下大小
if(x>mid+1&&tree[rt<<1|1])///如果大于中值，那么可以试着去右节点去找
{
int ans=Pre(x,rt<<1|1,mid+1,r);
///找第一个r<p的区间
if(ans==0)///说明在右节点找不到那么就回左节点找
return Pre(x,rt<<1,l,mid);
return ans;
}
///如果不满足x>mid的话，或者右节点没有数字，那么就回左节点去找
return Pre(x,rt<<1,l,mid);
}
int Findnext(int rt,int l,int r)
{
if(l==r)return l;
int mid=l+r>>1;
if(tree[rt<<1|1])return Findnext(rt<<1|1,mid+1,r);
return Findnext(rt<<1,l,mid);
}
int Next(int x,int rt,int l,int r)///优先找小的数字
{
if(x<l)///找到第一个这样的区间
{
if(tree[rt])return Findnext(rt,l,r);
return 0;
}
int mid=l+r>>1;
if(x<mid&&tree[rt<<1])
{
int ans=Next(x,rt<<1,l,mid);
if(ans==0)return Next(x,rt<<1|1,mid+1,r);
return ans;
}
return Next(x,rt<<1|1,mid+1,r);
}
int main()
{
int n=read();
rep(i,1,n)op[i]=read(),x[i]=read(),lsh[i]=x[i];
sort(lsh+1,lsh+1+n);
int len=unique(lsh+1,lsh+1+n)-lsh-1;
rep(i,1,n)
{
id[i]=lower_bound(lsh+1,lsh+1+len,x[i])-lsh;
num[id[i]]=x[i];///双向映射
}
rep(i,1,n)
{
if(op[i]==1)Update(id[i],1,1,1,n);
else if(op[i]==2)Update(id[i],-1,1,1,n);
else if(op[i]==3)
{
printf("%d\n",Rank(id[i],1,1,n)+1);
}
else if(op[i]==4)
{
printf("%d\n",num[Kth(id[i],1,1,n)]);
}
else if(op[i]==5)
{
printf("%d\n",num[Pre(id[i],1,1,n)]);
}
else printf("%d\n",num[Next(id[i],1,1,n)]);
}
return 0;
}
```
离散化了，数组都是1e5级别的，还能MLE的吗
by YuanZhizheng @ 2021-04-09 21:19:58
没事了，是函数运行爆栈了
by YuanZhizheng @ 2021-04-09 21:27:22