总会在答案上有一些莫名的少1.
操作如下：
0 x，把 x（0 ≤x≤10^9 ) 加入 S 。
1 x，删除 S 中的一个 x，保证删除的数在 S 中一定存在 。
2 k，求 S 中第 k（1≤k≤|S|）小 。
3 x，求 S 中有多少个数小于 x（0≤x≤10^9） 。
4 x，求S 中小于 x（0≤x≤10^9 )的最大数，如果不存在，输出 -1。
5 x，求S 中大于 x（0≤x≤10^9 )的最小数，如果不存在，输出 -1。
代码中数组大致如下定义
father数组：存储该节点的父节点
son数组：son[x,1]表示x节点的左儿子,son[x,2]表示x节点的右儿子
Data数组：存储节点的值
value数组：存储该节点的值出现了几次
count数组：count[x]表示以x为根的子树结点数量
下面是代码
#include<bits/stdc++.h>
using namespace std;
#define N 1000500
int Count[N],son[N][2],father[N],root,data[N],value[N],tot=0,n;
void update(int x);
inline void Rotate(int x,int w)
{
int y;
y=father[x];
Count[y]=Count[y]-Count[x]+Count[son[x][w]];
Count[x]=Count[x]+Count[y]-Count[son[x][w]];
son[y][3-w]=son[x][w];
if(son[x][w])
father[son[x][w]]=y;
father[x]=father[y];
if(father[y])
{
if(y==son[father[y]][1])
son[father[y]][1]=x;
if(y==son[father[y]][2])
son[father[y]][2]=x;
}
father[y]=x;
son[x][w]=y;
update(x);update(y);
}
inline void splay(int x)
{
int y;
while(father[x]!=0)
{
y=father[x];
if(father[y]==0)
{
if(x==son[y][1])
Rotate(x,2);
else
Rotate(x,1);
}
else
{
if(y==son[father[y]][1])
{
if(x==son[y][1])
{
Rotate(y,2);
Rotate(x,2);
}
else
{
Rotate(x,1);
Rotate(x,2);
}
}
else
{
if(x==son[y][1])
{
Rotate(x,2);
Rotate(x,1);
}
else
{
Rotate(y,1);
Rotate(x,1);
}
}
}
}
root=x;
}
inline int Search(int x,int w)
{
while(data[x]!=w)
{
if(w==data[x])
return x;
if(w<data[x])
{
if(!son[x][1])
break;
x=son[x][1];
}
else
{
if(son[x][2]==0)
break;
x=son[x][2];
}
}
return x;
}
inline void Insert(int w)
{
int k,kk;bool flag;
if(!tot)
{
tot=1;
father[1]=0;
data[1]=w;
Count[1]=1;
root=1;
value[1]=1;
return;
}
k=Search(root,w);
if(data[k]==w)
{
value[k]++;
kk=k;
flag=true;
}
else
{
tot++;
data[tot]=w;
father[tot]=k;
Count[tot]=value[tot]=1;
if(data[k]>w)
son[k][1]=tot;
else
son[k][2]=tot;
flag=0;
}
while(k)
{
Count[k]++;
k=father[k];
}
if(flag)
splay(kk);
else
splay(tot);
}
int Min(int x);int Max(int x);
void eupdate(int x);
void update(int x)
{
eupdate(x);
if(father[x])
eupdate(father[x]);
}
void eupdate(int x)
{
int y=0;
if(son[x][1]!=0)
y+=Count[son[x][1]];
if(son[x][2]!=0)
y+=Count[son[x][2]];
Count[x]=y+value[x];
}
inline int MaxMin(int x,int w)
{
if(w==1)
return Max(x);
return Min(x);
}
inline int Min(int x)
{
int MI=INT_MIN+1000;
int k,tmp;
k=Search(x,MI);
tmp=data[k];
if(k!=0)
splay(k);
return tmp;
}
inline int Max(int x)
{
int MA=INT_MAX-1000;
int k,tmp;
k=Search(x,MA);
tmp=data[k];
if(k!=0)
splay(k);
return tmp;
}
inline void del(int x)
{
int k,y;
k=Search(root,x);
if(!k)
return;
//if(data[k]!=x)
//splay(k);
else
{ splay(k);
if(value[k]>1)
{
value[k]--;
Count[k]--;
}
else
{
if(!son[k][1])
{
y=son[k][2];
son[k][2]=0;
Count[k]=0;
data[k]=0;
value[k]=0;
root=y;
father[root]=0;
}
else
{
father[son[k][1]]=0;
y=MaxMin(son[k][1],1);
son[root][2]=son[k][2];
Count[root]=Count[root]+Count[son[k][2]];
if(son[root][2]!=0)
father[son[root][2]]=root;
data[k]=son[k][1]=son[k][2]=value[k]=0;
}
}
}
}
inline int pred(int x)
{
int k;
k=Search(root,x);
splay(k);
if (data[k]<x)
return data[k];
int ans=Max(son[k][1]);
if(ans==0)
return -1;
return ans;
}
inline int succ(int x)
{
int k;
k=Search(root,x);
splay(k);
if (data[k]>x)
return data[k];
int ans=Min(son[k][2]);
if(ans==0)
return -1;
return ans;
}
inline int kth(int x,int w)
{
int i,tmp;
i=root;
while (!((x>=Count[son[i][w]]+1)&&(x<=Count[son[i][w]]+value[i]))&&(i!=0))
{
if (x>Count[son[i][w]]+value[i])
{
x=x-Count[son[i][w]]-value[i];
i=son[i][3-w];
}
else
i=son[i][w];
}
tmp=i;
splay(i);
return tmp;
}
inline int findnum(int x)
{
int k;
k=Search(root,x);
splay(k);
root=k;
return Count[son[k][1]];
}
int main()
{
cin>>n;
int opt,x;
for(int i=1;i<=n;i++)
{
cin>>opt>>x;
switch(opt)
{
case 0:Insert(x);break;
case 1:del(x);break;
case 3:cout<<findnum(x)<<endl;break;
case 2:cout<<data[kth(x,1)]<<endl;break;
case 4:cout<<pred(x)<<endl;break;
case 5:cout<<succ(x)<<endl;break;
}
}
}
不胜感激！
