题解 SP3273 【ORDERSET - Order statistic set】
引领天下
2019-01-17 18:04:48
这题目其实就是个平衡树裸题
那么我们就可以使用平板电视水过去
平板电视代码：
```cpp
#include<cstdio>
#include<ext/pb_ds/assoc_container.hpp>
//pb_ds库内置了红黑树（red-black tree）、伸展树（splay tree）和排序向量树（ordered-vector tree）。
//这些封装好的树都支持插入（insert）、删除（erase）、求kth（find_by_order）、求rank（order_of_key）操作，O(logn)内完成
using namespace std;
using namespace __gnu_pbds;
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*10+ch-'0';ch=getchar();}
return x*f;
}
tree<int,null_mapped_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>bbt;
//SPOJG++版本稍旧(4.3.2),需要写成null_mapped_type才可以(高级版本可以写null_type)
char in(){
for(char ch=getchar();;ch=getchar()) if(ch>='A'&&ch<='Z') return ch;
}
int main(){
char c;int x;
for(int T=read();T--;){
c=in();x=read();
if(c=='I')bbt.insert(x);//平衡树：插入
else if(c=='D')bbt.erase(x);//平衡树：删除
else if(c=='K'){
if(x<=bbt.size())
printf("%d\n",*bbt.find_by_order(x-1));//平衡树，查找
else puts("invalid");
}
else printf("%d\n",bbt.order_of_key(x));//计数
}
return 0;
}
```
然而SPOJ好像并不支持。
没关系，我们手打！
手打平衡树：
```cpp
#include<cstdio>
#include<cstdlib>
using namespace std;
const int MAXN=200005;
const int INF=0x3f3f3f3f;
struct Treap {
int tot,root;
int ch[MAXN][2],key[MAXN],pt[MAXN],size[MAXN];
Treap() {
tot=1;
root=0;
pt[0]=INF;
size[0]=0;
}
void rotate(int &x,int t) {
int y=ch[x][t];
ch[x][t]=ch[y][t^1];
ch[y][t^1]=x;
size[y]=size[x];
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
x=y;
}
bool insert(int &x,int k) {
if(!x) {
x=tot++;
ch[x][0]=ch[x][1]=0;
key[x]=k;
pt[x]=rand();
size[x]=1;
return true;
}
if(key[x]==k)
return false;
int t=key[x]<k;
if(!insert(ch[x][t],k))
return false;
++size[x];
if(pt[ch[x][t]]<pt[x])
rotate(x,t);
return true;
}
bool remove(int &x,int k) {
if(!x)
return false;
if(key[x]!=k) {
if(!remove(ch[x][key[x]<k],k))
return false;
--size[x];
} else if(!ch[x][0]&&!ch[x][1])
x=0;
else if(!ch[x][0])
x=ch[x][1];
else if(!ch[x][1])
x=ch[x][0];
else {
rotate(x,pt[ch[x][0]]>pt[ch[x][1]]);
if(!remove(ch[x][key[x]<k],k))
return false;
--size[x];
}
return true;
}
void insert(int k) {
insert(root,k);
}
void remove(int k) {
remove(root,k);
}
int getKth(int k) {
int x=root;
while(size[ch[x][0]]+1!=k)
if(k<size[ch[x][0]]+1)
x=ch[x][0];
else {
k-=size[ch[x][0]]+1;
x=ch[x][1];
}
return key[x];
}
int getRank(int k) {
int ret=0,x=root;
while(x)
if(k<key[x])
x=ch[x][0];
else {
ret+=size[ch[x][0]]+1;
x=ch[x][1];
}
return ret;
}
} treap;
int main() {
int n,num;
char c;
scanf("%d",&n);
while(n--) {
scanf(" %c%d",&c,&num);
switch(c) {
case 'I':
treap.insert(num);
break;
case 'D':
treap.remove(num);
break;
case 'K':
num<=treap.size[treap.root]?printf("%d\n",treap.getKth(num)):puts("invalid");
break;
case 'C':
printf("%d\n",treap.getRank(num-1));
break;
}
}
}
```