题意：
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
1.n的数据范围：n<=100000
2.每个数的数据范围：[-1e7,1e7]
思路：为了学LCT才去学的splay
看来又入新坑了
插入的时候把x的前一个（注意不是前驱）转到根，后一个（不是后继）转到根的右儿子，
这样根结点右儿子的左儿子就是要插入的x，直接插入
删除时候类似，这样可以保证每次只删去一个数
var t:array[..,..]of longint;
sum,b,fa,num:array[..]of longint;
n,i,x,y,root,cnt,save,tmp,m:longint;
flag:boolean; procedure pushup(x:longint);
var l,r:longint;
begin
l:=t[x,]; r:=t[x,];
sum[x]:=sum[l]+sum[r]+;
end; procedure rotate(x:longint;var k:longint);
var y,z,l,r:longint;
begin
y:=fa[x]; z:=fa[y];
if t[y,]=x then l:=
else l:=;
r:=l xor ;
if y<>k then
begin
if t[z,]=y then t[z,]:=x
else t[z,]:=x;
end
else k:=x;
fa[t[x,r]]:=y; fa[x]:=z; fa[y]:=x;
t[y,l]:=t[x,r]; t[x,r]:=y;
pushup(y);
pushup(x);
end; procedure splay(x:longint;var k:longint);
var y,z:longint;
begin
while x<>k do
begin
y:=fa[x]; z:=fa[y];
if y<>k then
begin
if (t[z,]=y)xor(t[y,]=x) then rotate(x,k)
else rotate(y,k);
end
else k:=x;
rotate(x,k);
end; end; function pred(x:longint):longint;
var k,last:longint;
begin
k:=root; last:=num[root];
while k<> do
begin
if num[k]<x then begin last:=num[k]; k:=t[k,]; end
else k:=t[k,];
end;
exit(last);
end; function succ(x:longint):longint;
var k,last:longint;
begin
k:=root; last:=num[root];
while k<> do
begin
if num[k]>x then begin last:=num[k]; k:=t[k,]; end
else k:=t[k,];
end;
exit(last);
end; function rank(x:longint):longint;
var k:longint;
begin
x:=pred(x);
k:=root; rank:=;
while k> do
begin
if num[k]<=x then begin rank:=rank+sum[t[k,]]+; k:=t[k,]; end
else k:=t[k,];
end;
inc(rank);
end; function kth(x:longint):longint;
var tmp,k:longint;
begin
k:=root;
while true do
begin
tmp:=sum[t[k,]]+;
if tmp=x then exit(k);
if tmp>x then k:=t[k,]
else
begin
k:=t[k,]; x:=x-tmp;
end;
end;
end; function find(x:longint):longint;
var k:longint;
begin
k:=root;
while true do
begin
if num[k]=x then exit(k)
else if num[k]<x then k:=t[k,]
else k:=t[k,];
end;
end; procedure ins(x:longint);
var tmp,l,r,k1:longint;
begin
tmp:=rank(x);
l:=kth(tmp-);
r:=kth(tmp);
splay(l,root);
splay(r,t[root,]);
k1:=t[root,];
inc(cnt); t[k1,]:=cnt; fa[cnt]:=k1; sum[cnt]:=; num[cnt]:=x;
// inc(sum[k1]);
// inc(sum[root]);
end; procedure del(x:longint);
var k1,k2,l,r:longint;
begin
tmp:=rank(x);
l:=kth(tmp-);
r:=kth(tmp+);
splay(l,root);
splay(r,t[root,]);
k1:=t[root,]; k2:=t[k1,];
sum[k1]:=sum[t[k1,]]+; fa[k2]:=; sum[k2]:=;
t[k1,]:=; fa[k2]:=; sum[k2]:=; t[k2,]:=; t[k2,]:=; end; begin
assign(input,'bzoj3224.in'); reset(input);
assign(output,'bzoj3224.out'); rewrite(output);
readln(n);
num[]:=maxlongint; sum[]:=; t[,]:=; t[,]:=;
num[]:=-maxlongint; sum[]:=; fa[]:=;
num[]:=maxlongint; sum[]:=; fa[]:=; root:=; cnt:=;
for i:= to n do
begin
readln(x,y);
case x of
:
begin
ins(y);
inc(m);
end;
:
begin
del(y);
dec(m);
end; :writeln(rank(y)-); :writeln(num[kth(y+)]);
:writeln(pred(y));
:writeln(succ(y));
end;
end;
close(input);
close(output);
end.
UPD(2018.9.15）：C++
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair
#define N 500000
#define MOD 1000000007
#define eps 1e-8
#define pi acos(-1)
#define oo 2e9 int t[N][],size[N],fa[N],num[N],root,cnt; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} void pushup(int x)
{
size[x]=size[t[x][]]+size[t[x][]]+;
} void rotate(int x,int &k)
{
int y=fa[x];
int z=fa[y];
int l;
if(t[y][]==x) l=;
else l=;
int r=l^;
if(y!=k)
{
if(t[z][]==y) t[z][]=x;
else t[z][]=x;
}
else k=x;
fa[t[x][r]]=y; fa[x]=z; fa[y]=x;
t[y][l]=t[x][r]; t[x][r]=y;
pushup(y);
pushup(x);
} void splay(int x,int &k)
{
while(x!=k)
{
int y=fa[x];
int z=fa[y];
if(y!=k)
{
if((t[z][]==y)^(t[y][]==x)) rotate(x,k);
else rotate(y,k);
}
else k=x;
rotate(x,k);
}
} int pred(int x)
{
int k=root;
int last=num[root];
while(k)
{
if(num[k]<x){last=num[k]; k=t[k][];}
else k=t[k][];
}
return last;
} int succ(int x)
{
int k=root;
int last=num[root];
while(k)
{
if(num[k]>x){last=num[k]; k=t[k][];}
else k=t[k][];
}
return last;
} int rank(int x)
{
x=pred(x);
int k=root;
int s=;
while(k)
{
if(num[k]<=x){s+=size[t[k][]]+; k=t[k][];}
else k=t[k][];
}
s++;
return s;
} int kth(int x)
{
int k=root;
while()
{
int tmp=size[t[k][]]+;
if(tmp==x) return k;
if(tmp>x) k=t[k][];
else{k=t[k][]; x-=tmp;}
}
} void Insert(int x)
{
int tmp=rank(x);
int l=kth(tmp-);
int r=kth(tmp);
splay(l,root);
splay(r,t[root][]);
int k=t[root][];
t[k][]=++cnt; fa[cnt]=k; size[cnt]=; num[cnt]=x;
} void Delete(int x)
{
int tmp=rank(x);
int l=kth(tmp-);
int r=kth(tmp+);
splay(l,root);
splay(r,t[root][]);
int k1=t[root][];
int k2=t[k1][];
size[k1]=size[t[k1][]]+; t[k1][]=;
fa[k2]=; size[k2]=;
t[k2][]=; t[k2][]=;
} int main()
{
//freopen("bzoj3224.in","r",stdin);
//freopen("bzoj3224.out","w",stdout);
int n;
scanf("%d",&n);
num[]=-oo; size[]=; t[][]=;
num[]=oo; size[]=; fa[]=;
root=; cnt=;
for(int i=;i<=n;i++)
{
int x,y,ans;
scanf("%d%d",&x,&y);
if(x==) Insert(y);
if(x==) Delete(y);
if(x==)
{
ans=rank(y)-;
printf("%d\n",ans);
}
if(x==)
{
ans=num[kth(y+)];
printf("%d\n",ans);
}
if(x==)
{
ans=pred(y);
printf("%d\n",ans);
}
if(x==)
{
ans=succ(y);
printf("%d\n",ans);
}
}
}