Input
多组数据（整个文件以输入 -1 结束） 对于每组数据，有若干行（最多100000行），表示的意义如下： 【A】 insert x 【B】 delete x 【C】 predecessor x 【D】 successor x 【E】 Kth x 【F】 rank x 这6种操作的意义与上面的定义相对应！ 【G】 print 表示从小到大输出序列中的所有元素 【H】 end 表示结束本组数据 每组输入数据后有一空行！
Output
对于以上8种操作，分别输出对应信息，如下： 【A】 insert x 不用输出任何信息 【B】 delete x 如果x存在，则删除x，否则输出 Input Error 【C】 predecessor x 如果x不存在，输出 Input Error；否则如果x是序列中的最小元素，输出对应信息（见样例），否则输出x的前继元素 【D】 successor x 如果x不存在，输出 Input Error；否则如果x是序列中的最大元素，输出对应信息（见样例），否则输出x的后继元素 【E】 Kth x 如果x不合法，输出 Input Error；否则输出第Kth小的元素（见样例） 【F】 rank x 如果x不存在，输出 Input Error；否则输出x的排名（见样例） 【G】 print 从小到大输出序列中的所有元素，每个元素后加一个逗号，并在最后加上 end of print（见样例） 【H】 end 输出 end of this test
insert 20 insert 5 insert 1 insert 15 insert 9 insert 25 insert 23 insert 30 insert 35 print Kth 0 Kth 1 Kth 3 Kth 5 Kth 7 Kth 9 Kth 10 rank 1 rank 3 rank 5 rank 15 rank 20 rank 30 rank 31 rank 35 successor 15 successor 35 successor 25 successor 26 predecessor 1 predecessor 20 predecessor 23 predecessor 15 predecessor 111 delete 9 delete 15 delete 25 delete 23 delete 20 print Kth 3 Kth 4 rank 30 rank 35 end -1
1,5,9,15,20,23,25,30,35,end of print Input Error The 1_th element is 1 The 3_th element is 9 The 5_th element is 20 The 7_th element is 25 The 9_th element is 35 Input Error The rank of 1 is 1_th Input Error The rank of 5 is 2_th The rank of 15 is 4_th The rank of 20 is 5_th The rank of 30 is 8_th Input Error The rank of 35 is 9_th The successor of 15 is 20 35 is the maximum The successor of 25 is 30 Input Error 1 is the minimum The predecessor of 20 is 15 The predecessor of 23 is 20 The predecessor of 15 is 9 Input Error 1,5,30,35,end of print The 3_th element is 30 The 4_th element is 35 The rank of 30 is 3_th The rank of 35 is 4_th end of this test
【解题方法】Treap.
【AC 代码】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF=0x3FFFFFFF;
struct Treap
{
int siz;
int key,fix;
Treap *ch[2];
Treap(int key)
{
siz=1;
fix=rand()*rand();
this->key=key;
ch[0]=ch[1]=NULL;
}
int compare(int x) const
{
if(x==key) return -1;
return x<key? 0:1;
}
void Maintain()
{
siz=1;
if(ch[0]!=NULL) siz+=ch[0]->siz;
if(ch[1]!=NULL) siz+=ch[1]->siz;
}
};
void Rotate(Treap* &t,int d)
{
Treap *k=t->ch[d^1];
t->ch[d^1]=k->ch[d];
k->ch[d]=t;
t->Maintain(); //必须先维护t，再维护k，因为此时t是k的子节点
k->Maintain();
t=k;
}
void Insert(Treap* &t,int x)
{
if(t==NULL) t=new Treap(x);
else
{
if(x==t->key)
return;
int d=t->compare(x); //如果值相等的元素只插入一个
//;int d=x < t->key ? 0:1; //如果值相等的元素都插入
Insert(t->ch[d],x);
if(t->ch[d]->fix > t->fix)
Rotate(t,d^1);
}
t->Maintain();
}
//一般来说，在调用删除函数之前要先用Find()函数判断该元素是否存在
void Delete(Treap* &t,int x)
{
int d=t->compare(x);
if(d==-1)
{
Treap *tmp=t;
if(t->ch[0]==NULL)
{
t=t->ch[1];
delete tmp;
tmp=NULL;
}
else if(t->ch[1]==NULL)
{
t=t->ch[0];
delete tmp;
tmp=NULL;
}
else
{
int k=t->ch[0]->fix > t->ch[1]->fix ? 1:0;
Rotate(t,k);
Delete(t->ch[k],x);
}
}
else Delete(t->ch[d],x);
if(t!=NULL) t->Maintain();
}
bool Find(Treap *t,int x)
{
while(t!=NULL)
{
int d=t->compare(x);
if(d==-1) return true;
t=t->ch[d];
}
return false;
}
int Kth(Treap *t,int k)
{
if(t==NULL||k<=0||k>t->siz)
return -1;
if(t->ch[0]==NULL&&k==1)
return t->key;
if(t->ch[0]==NULL)
return Kth(t->ch[1],k-1);
if(t->ch[0]->siz>=k)
return Kth(t->ch[0],k);
if(t->ch[0]->siz+1==k)
return t->key;
return Kth(t->ch[1],k-1-t->ch[0]->siz);
}
int Rank(Treap *t,int x)
{
int r;
if(t->ch[0]==NULL) r=0;
else r=t->ch[0]->siz;
if(x==t->key) return r+1;
if(x<t->key)
return Rank(t->ch[0],x);
return r+1+Rank(t->ch[1],x);
}
int sub(Treap *t,int x)
{
int ret=-INF;
while(t!=NULL){
if(t->key>x){
ret=t->key;
t=t->ch[0];
}else{
t=t->ch[1];
}
}
return ret;
}
int pre(Treap *t,int x)
{
int ret=INF;
while(t!=NULL)
{
if(t->key<x){
ret=t->key;
t=t->ch[1];
}
else{
t=t->ch[0];
}
}
return ret;
}
int Depth(Treap *t)
{
if(t==NULL) return -1;
int l=Depth(t->ch[0]);
int r=Depth(t->ch[1]);
return l<r ? (r+1):(l+1);
}
void DeleteTreap(Treap* &t)
{
if(t==NULL) return;
if(t->ch[0]!=NULL) DeleteTreap(t->ch[0]);
if(t->ch[1]!=NULL) DeleteTreap(t->ch[1]);
delete t;
t=NULL;
}
void Print(Treap *t)
{
if(t==NULL) return;
Print(t->ch[0]);
cout<<t->key<<",";
Print(t->ch[1]);
}
int main()
{
Treap *root=NULL;
char s[20];
while(scanf("%s",s)!=EOF)
{
int x;
if(strcmp(s,"-1")==0)
break;
else if(strcmp(s,"print")==0)
{
Print(root);
printf("end of print\n");
}
else if(strcmp(s,"end")==0)
{
DeleteTreap(root);
printf("end of this test\n");
}
else if(strcmp(s,"insert")==0)
{
scanf("%d",&x);
Insert(root,x);
}
else if(strcmp(s,"delete")==0)
{
scanf("%d",&x);
if(Find(root,x))
{
Delete(root,x);
}
else
{
printf("Input Error\n");
}
}
else if(strcmp(s,"predecessor")==0)
{
scanf("%d",&x);
if(Find(root,x))
{
int ans=pre(root,x);
if(ans==INF)
{
printf("%d is the minimum\n",x);
}
else
{
printf("The predecessor of %d is %d\n",x,ans);
}
}
else
{
printf("Input Error\n");
}
}
else if(strcmp(s,"successor")==0)
{
scanf("%d",&x);
if(Find(root,x))
{
int ans=sub(root,x);
if(ans==-INF)
printf("%d is the maximum\n",x);
else
{
printf("The successor of %d is %d\n",x,ans);
}
}
else
{
printf("Input Error\n");
}
}
else if(strcmp(s,"Kth")==0)
{
scanf("%d",&x);
if(root==NULL)
{
printf("Input Error\n");
continue;
}
if(root->siz<x||x<=0)
printf("Input Error\n");
else
printf("The %d_th element is %d\n",x,Kth(root,x));
}
else if(strcmp(s,"rank")==0)
{
scanf("%d",&x);
if(Find(root,x))
{
printf("The rank of %d is %d_th\n",x,Rank(root,x));
}
else
{
printf("Input Error\n");
}
}
}
}
京公网安备 11010502036488号