首页 > 代码库 > HDOJ 3436 Queue-jumpers
HDOJ 3436 Queue-jumpers
N的范围很大,但Q的范围比较小.可以把TOP,QUERY操作用到的点分离出来,没用到的段缩成点
对于TOP 把x转到根,删除后加到开头位置
对于QUERY 旋转到根直接输出
对于RANK,递归
Queue-jumpers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2216 Accepted Submission(s): 561
Problem Description
Ponyo and Garfield are waiting outside the box-office for their favorite movie. Because queuing is so boring, that they want to play a game to kill the time. The game is called “Queue-jumpers”. Suppose that there are N people numbered from 1 to N stand in a line initially. Each time you should simulate one of the following operations:
1. Top x :Take person x to the front of the queue
2. Query x: calculate the current position of person x
3. Rank x: calculate the current person at position x
Where x is in [1, N].
Ponyo is so clever that she plays the game very well while Garfield has no idea. Garfield is now turning to you for help.
1. Top x :Take person x to the front of the queue
2. Query x: calculate the current position of person x
3. Rank x: calculate the current person at position x
Where x is in [1, N].
Ponyo is so clever that she plays the game very well while Garfield has no idea. Garfield is now turning to you for help.
Input
In the first line there is an integer T, indicates the number of test cases.(T<=50)
In each case, the first line contains two integers N(1<=N<=10^8), Q(1<=Q<=10^5). Then there are Q lines, each line contain an operation as said above.
In each case, the first line contains two integers N(1<=N<=10^8), Q(1<=Q<=10^5). Then there are Q lines, each line contain an operation as said above.
Output
For each test case, output “Case d:“ at first line where d is the case number counted from one, then for each “Query x” operation ,output the current position of person x at a line, for each “Rank x” operation, output the current person at position x at a line.
Sample Input
3 9 5 Top 1 Rank 3 Top 7 Rank 6 Rank 8 6 2 Top 4 Top 5 7 4 Top 5 Top 2 Query 1 Rank 6
Sample Output
Case 1: 3 5 8 Case 2: Case 3: 3 6
Author
wzc1989
Source
2010 ACM-ICPC Multi-University Training Contest(1)——Host by FZU
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=200200; char op[maxn][10]; int number[maxn]; int n; int s[maxn],e[maxn]; int p[maxn]; /***************SPLAY*********************/ int ch[maxn][2],num[maxn],sz[maxn],pre[maxn]; int tot1,root; void NewNode(int& x,int father,int k) { x=k; sz[x]=num[x]=e[x]-s[x]+1; ch[x][1]=ch[x][0]=0; pre[x]=father; } void Push_Up(int x) { sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+num[x]; } void Build(int& x,int l,int r,int fa) { if(l>r) return ; int mid=(l+r)/2; NewNode(x,fa,mid); Build(ch[x][0],l,mid-1,x); Build(ch[x][1],mid+1,r,x); Push_Up(x); } void Init() { root=0; ch[root][0]=ch[root][1]=pre[root]=sz[root]=num[root]=0; Build(root,1,n,0); Push_Up(root); } void Rotate(int x,int kind) { int y=pre[x]; ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; pre[y]=x; ch[x][kind]=y; Push_Up(y); } void Splay(int r,int goal) { while(pre[r]!=goal) { if(pre[pre[r]]==goal) { Rotate(r,ch[pre[r]][0]==r); } else { int y=pre[r]; int kind=(ch[pre[y]][0]==y); if(ch[y][kind]==r) Rotate(r,!kind); else Rotate(y,kind); Rotate(r,kind); } } Push_Up(r); if(goal==0) root=r; } int Get_Min(int r) { while(ch[r][0]) r=ch[r][0]; return r; } void Remove_Root() { if(ch[root][1]==0||ch[root][0]==0) { root=ch[root][1]+ch[root][0]; pre[root]=0; return ; } int k=Get_Min(ch[root][1]); Splay(k,root); ch[ch[root][1]][0]=ch[root][0]; root=ch[root][1]; pre[ch[root][0]]=root; pre[root]=0; Push_Up(root); } int Bin(int x) { int low=1,high=n,mid; while(low<=high) { mid=(low+high)/2; if(s[mid]<=x&&x<=e[mid]) return mid; if(s[mid]>x) high=mid-1; else low=mid+1; } return -1; } /************doit*********/ void TOP(int x) { int y=Bin(x); Splay(y,0); Remove_Root(); Splay(Get_Min(root),0); ch[y][0]=0; ch[y][1]=root; pre[root]=y;root=y; pre[root]=0; Push_Up(root); } int QUERY(int x) { int y=Bin(x); Splay(y,0); return sz[ch[root][0]]+1; } int RANK(int r,int x) { int t=sz[ch[r][0]]; if(x<=t) return RANK(ch[r][0],x); else if(x<=t+num[r]) { return s[r]+x-t-1; } else return RANK(ch[r][1],x-t-num[r]); } /*********DEBUG***********/ void showit(int x) { if(x) { showit(ch[x][0]); printf("结点: %2d 左儿子: %2d 右儿子: %2d 父结点: %2d size: %2d num: %2d \n", x,ch[x][0],ch[x][1],pre[x],sz[x],num[x]); showit(ch[x][1]); } } void debug() { cout<<"root : "<<root<<endl; showit(root); } int main() { int T_T,cas=1; scanf("%d",&T_T); while(T_T--) { printf("Case %d:\n",cas++); int t=0; int nn,mm; scanf("%d%d",&nn,&mm); for(int i=0;i<mm;i++) { scanf("%s%d",op[i],number+i); if(op[i][0]==‘T‘||op[i][0]==‘Q‘) { p[t++]=number[i]; } } n=0; p[t++]=1;p[t++]=nn; sort(p,p+t); t=unique(p,p+t)-p; for(int i=0;i<t;i++) { if(i!=0&&p[i]-1!=p[i-1]) { n++; s[n]=p[i-1]+1; e[n]=p[i]-1; } n++; s[n]=e[n]=p[i]; } Init(); for(int i=0;i<mm;i++) { if(op[i][0]==‘T‘) TOP(number[i]); else if(op[i][0]==‘Q‘) printf("%d\n",QUERY(number[i])); else printf("%d\n",RANK(root,number[i])); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。