一 题面
二 分析
比较明显是可以用平衡二叉搜索树(splay)做的。
用权值线段树做，前提就是要先离散化，因为权值线段树维护的值域信息。
板子。
三 AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <fstream> using namespace std;
#define lson rt<<1
#define rson rt<<1|1 const int MAXN = 1e5 + ;
int N, op[MAXN], opx[MAXN];
struct Node
{
int id, x;
}Data[MAXN];
int A[MAXN]; int segTree[MAXN<<]; bool Cmpx(const Node &a, const Node &b)
{
return a.x < b.x;
} //p更新的位置,v=-1表示减，v=1表示加
void Update(int p, int v, int rt, int l, int r)
{
segTree[rt] += v;
if(l == r) return;
int mid = (l+r)>>;
if(p <= mid) Update(p, v, lson, l, mid);
else Update(p, v, rson, mid+, r);
}
//第K小
int Kth(int K, int rt, int l, int r)
{
if(l == r)
return l;
int mid = (l+r)>>;
if(segTree[lson] >= K)
return Kth(K, lson, l, mid);
else
return Kth(K-segTree[lson], rson, mid+, r);
}
//数字v的排名
//统计小于v的数的个数
int Rank(int v, int rt, int l, int r)
{
if(r < v)
return segTree[rt];
int mid = (l+r)>>, res = ;
res += Rank(v, lson, l, mid);
//相当于mid+1 < v 那么左边可能还有
if(mid < v-)
res += Rank(v, rson, mid+, r);
return res;
}
//找最右边的数
int Findr(int rt, int l, int r)
{
if(l == r)
return l;
int mid = (l+r)>>;
if(segTree[rson]) return Findr(rson, mid + , r);
return Findr(lson, l, mid);
}
//前驱
int Pre(int v, int rt, int l, int r)
{
if(r < v)
{
if(segTree[rt]) return Findr(rt, l, r);
return ;
}
int mid = (l+r)>>, res;
//如果v > mid+1那么意味着mid+1或后面的数有可能是前驱
if(mid < v- && segTree[rson] && (res=Pre(v,rson,mid+,r)))
return res;
return Pre(v, lson, l, mid);
}
//找最左边的数
int Findl(int rt, int l, int r)
{
if(l == r)
return l;
int mid = (l+r)>>;
if(segTree[lson]) return Findl(lson, l, mid);
return Findl(rson, mid+, r);
}
//后继
int Nex(int v, int rt, int l, int r)
{
if(v < l)
{
if(segTree[rt]) return Findl(rt, l, r);
return ;
}
int mid = (l+r)>>, res;
//如果mid > v表示左子树的数可能是后继
if(v < mid && segTree[lson] && (res=Nex(v,lson,l,mid)))
return res;
return Nex(v, rson, mid + , r);
} int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d", &N);
for(int i = ; i <= N; i++)
{
scanf("%d %d", &op[i], &Data[i].x);
Data[i].id = i;
}
//离散化预处理
sort(Data + , Data + N + , Cmpx);
int cnt = ;
A[cnt] = Data[].x;
opx[Data[].id] = cnt;
for(int i = ; i <= N; i++)
{
if(Data[i].x != Data[i - ].x)
{
cnt++;
}
A[cnt] = Data[i].x;
opx[Data[i].id] = cnt;
}
//建树
memset(segTree, , sizeof(segTree) );
for(int i = ; i <= N; i++)
{
switch(op[i])
{
case : Update(opx[i], , , , cnt); break;
case : Update(opx[i], -, , , cnt); break;
case : printf("%d\n", Rank(opx[i], , , cnt)+); break;
//这里注意第K个数也离散化了！！！
case : printf("%d\n", A[ Kth(A[opx[i]], , , cnt)] ); break;
case : printf("%d\n", A[ Pre(opx[i], , , cnt)] ); break;
case : printf("%d\n", A[ Nex(opx[i], , , cnt)] ); break;
}
} return ;
}