本文主要是介绍poj3481 Double Queue splay，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：对于某种队列有3中操作，cmd =1 ，将优先级为p的顾客k加入队列 。 cmd=2,将队列优先级最高的顾客丢出队列并输出顾
客，cmd=3,将队列优先级最低的顾客丢出队列并输出顾客。
思路：用了splay，结果压根都没旋转操作。。找优先级小的就找最左端，然后把对应指针修改就行，找优先级大的就找最右端，然
后把对应指针修改就行。所以其实BIT就行了。详见代码：
// file name: poj3481.cpp //
// author: kereo //
// create time: 2014年08月28日 星期四 18时52分59秒 //
//***********************************//
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1000000+100;
const int inf=0x3fffffff;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
int n,top,cnt;
int st[MAXN];
struct node
{int val,s;node *fa,*ch[2];
}nod[MAXN],nil,*root,*null;
map<int,int>mp;
struct Splay
{void init(){top=cnt=0;nil.s=nil.val=0; null=&nil;root=null;}void newnode(node *&x,node *f,int val){if(top) x=&nod[st[--top]];else x=&nod[cnt++];x->s=1; x->val=val; x->fa=f; x->ch[0]=x->ch[1]=null;}/*void push_up(node *x){x->s=1;if(x->ch[0]!=null) x->s+=x->ch[0]->s;if(x->ch[1]!=null) x->s+=x->ch[1]->s;}*/void rotate(node *x,int d){node *y=x->fa;//push_down(y); push_down(x);y->ch[d^1]=x->ch[d];if(x->ch[d]!=null) x->ch[d]->fa=y;x->fa=y->fa;if(y->fa!=null){int d1=y->fa->ch[0] == y ? 0 : 1;y->fa->ch[d1]=x;}x->ch[d]=y; y->fa=x;//push_up(y);}void splay(node *x,node *f){while(x->fa!=f){//push_down(x);node *y=x->fa;if(y->fa == f){int d=y->ch[0] == x ? 1 : 0;rotate(x,d);}else{int d=y->fa->ch[0] == y ? 1 : 0;if(y->ch[d] == x){ //之字型rotate(x,d^1); rotate(x,d);}else{ //一字型rotate(y,d); rotate(x,d);}}}//push_up(x);if(f == null) root=x;}void insert(node *&x,node *f,int val){if(x == null){newnode(x,f,val);//splay(x,null);return ;}int d=val< x->val ? 0 : 1;insert(x->ch[d],x,val);}void Delete(node *x){splay(x,null); st[top++]=x-nod;//printf("#####x->ch[0]->val=%d x->val=%d x->ch[1]->val=%d root->val=%d \n",x->ch[0]->val,x->val,x->ch[1]->val,root->val);if(x->ch[0] == null){//printf("haha1\n");if(x->ch[1] == null){root=null;}else{root=x->ch[1];x=x->ch[1];x->fa=null;}}else{//printf("haha2\n");node *y=x->ch[0];//printf("$$$$$$x->ch[0]->val = %d\n",y->val);while(y->ch[1]!=null) y=y->ch[1];splay(y,x);y->ch[1]=x->ch[1];if(x->ch[1]!=null)x->ch[1]->fa=y;y->fa=null; root=x=y;//push_up(y);}}//---------------------------------------------------------------//int get_prefix(node *x){if(x == null) return 0;//printf("(2)x->ch[0]->val=%d x->val=%d x->ch[1]->val=%d\n",x->ch[0]->val,x->val,x->ch[1]->val);node *par=x;while(x->ch[0]!=null) par=x,x=x->ch[0];//printf("(3) x->val=%d\n ",x->val);if(root == x) root=x->ch[1];par->ch[0]=x->ch[1];x->ch[1]->fa=par;int ans=x->val;//Delete(x);return ans;}int get_suffix(node *x){if(x == null) return 0;//printf("!!x->ch[0]->val=%d x->val=%d x->ch[1]->val=%d\n",x->ch[0]->val,x->val,x->ch[1]->val);node *par=x;while(x->ch[1]!=null) par=x,x=x->ch[1];if(root == x) root=x->ch[0];par->ch[1]=x->ch[0]; x->ch[0]->fa=par;int ans=x->val;//printf("!!!x->ch[0]->val=%d x->val=%d x->ch[1]->val=%d\n",x->ch[0]->val,x->val,x->ch[1]->val);//printf("******ans=%d\n",ans);//Delete(x);//printf("!!!x->ch[0]->val=%d x->val=%d x->ch[1]->val=%d\n",x->ch[0]->val,x->val,x->ch[1]->val);return ans;}
}spt;
int main()
{int cmd;spt.init(); mp.clear();mp[0]=0;while(~scanf("%d",&cmd) && cmd){if(cmd == 1){int k,p;scanf("%d%d",&k,&p);mp[p]=k;spt.insert(root,null,p);//spt.splay(x,null);//printf("root->ch[0]->val=%d root->val=%d root->ch[1]->val=%d\n",root->ch[0]->val,root->val,root->ch[1]->val);}if(cmd == 2){int ans=spt.get_suffix(root);//printf("root->ch[0]->val=%d root->val=%d root->ch[1]->val=%d\n",root->ch[0]->val,root->val,root->ch[1]->val);printf("%d\n",mp[ans]);}if(cmd == 3){//printf("(1)root->ch[0]->val=%d root->val=%d root->ch[1]->val=%d\n",root->ch[0]->val,root->val,root->ch[1]->val);int ans=spt.get_prefix(root);//printf("root->ch[0]->val=%d root->val=%d root->ch[1]->val=%d\n",root->ch[0]->val,root->val,root->ch[1]->val);printf("%d\n",mp[ans]);}}return 0;
}这篇关于poj3481 Double Queue splay的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
