本文主要是介绍HDU 3436 Queue-jumpers,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:
n个人站成一排 一开始是从1到n有序的 现在有三个操作 Top操作是将一个人排到队首 Query操作是询问某个人现在排第几 Rank操作是询问排某个位置的人是谁
思路:
将队伍扭来扭去… 很像splay的旋转吧(哪像了!!)
这是个不错的splay题…
首先 n很大 但是操作不多 想到离散化
离散化还有个技巧 我们发现只有top和query操作对单人进行 rank和人没什么关系
所以要把top和query操作的人单独拿出来 那么其他的人就可以用区间的形式来表示了
我们只需要开一个num数字来表示树上这个点(表示一个区间)包含几个人
然后就是对每个操作的处理 从简到难
Rank操作最简单 它根本和人没关系 只要找第k个位置就好了 不过我们现在的点表示的是一个区间
那也不难处理 开一个sum数组对num进行维护 就可以简单的找到第k个人所在区间 算一下他是谁就好
接着是Query操作 这个有点烦 因为我们不知道包含k这个人的区间是哪个
其实好解决 开个idx数字记录树上的点表示第几个区间 再开一个qu数组表示某个区间对应树上的点就好
找到了点然后呢? 把它转到根 然后sum[L(root)]+1就是答案!!
最后是Top 有了query的铺垫那么我们只要找到这个点 把它转到根 再把它的前驱转到根下面
删除根节点 再把删掉的这个点插到队首 一个top操作就完成了
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define keytree ch[ch[root][1]][0]
#define L(x) ch[x][0]
#define R(x) ch[x][1]
#define N 201000int T,t,n,m,tot,root;
int ch[N][2],pre[N],size[N],num[N],sum[N],idx[N],qu[N],a[N],s[N],e[N],op[N],opn[N];void newnode(int &u,int fa,int w)
{u=++tot;L(u)=R(u)=0;pre[u]=fa;size[u]=1;if(w){sum[u]=num[u]=e[w]-s[w]+1;idx[w]=u;qu[u]=w;}
}void up(int u)
{size[u]=size[L(u)]+size[R(u)]+1;sum[u]=num[u]+sum[L(u)]+sum[R(u)];
}void down(int u)
{
}void rotate(int u,int kind)
{int fa=pre[u];down(fa);down(u);ch[fa][!kind]=ch[u][kind];pre[ch[u][kind]]=fa;if(pre[fa]) ch[pre[fa]][ch[pre[fa]][1]==fa]=u;pre[u]=pre[fa];ch[u][kind]=fa;pre[fa]=u;up(fa);
}void splay(int u,int goal)
{int fa,kind;down(u);while(pre[u]!=goal){if(pre[pre[u]]==goal) rotate(u,L(pre[u])==u);else{fa=pre[u];kind=L(pre[fa])==fa;if(ch[fa][kind]==u){rotate(u,!kind);rotate(u,kind);}else{rotate(fa,kind);rotate(u,kind);}}}up(u);if(goal==0) root=u;
}int getkth(int u,int k)
{down(u);int tmp=size[L(u)]+1;if(tmp==k) return u;if(tmp>k) return getkth(L(u),k);else return getkth(R(u),k-tmp);
}int getkperson(int u,int k)
{down(u);int tmp=sum[L(u)];if(k>tmp&&k<=tmp+num[u]) return s[qu[u]]+k-tmp-1;if(tmp>=k) return getkperson(L(u),k);else return getkperson(R(u),k-tmp-num[u]);
}void build(int &u,int l,int r,int fa)
{if(l>r) return ;int mid=(l+r)>>1;newnode(u,fa,mid);build(L(u),l,mid-1,u);build(R(u),mid+1,r,u);up(u);
}void init()
{root=tot=0;L(root)=R(root)=pre[root]=size[root]=num[root]=sum[root]=idx[root]=0;newnode(root,0,0);newnode(R(root),root,0);build(keytree,1,n,R(root));up(R(root));up(root);
}int getpre(int u)
{down(u);u=L(u);down(u);while(R(u)){u=R(u);down(u);}return u;
}void remove()
{if(L(root)){int i=getpre(root);splay(i,root);R(i)=R(root);pre[R(root)]=i;root=L(root);pre[root]=0;up(root);}else{root=R(root);pre[root]=0;}
}void insert(int u)
{keytree=u;pre[u]=R(root);L(u)=R(u)=0;up(u);up(pre[u]);up(root);
}int main()
{//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);int i,j,k;char str[3];while(~scanf("%d",&T)){for(t=1;t<=T;t++){printf("Case %d:\n",t);scanf("%d%d",&n,&m);for(i=j=1;i<=m;i++){scanf("%s%d",str,&opn[i]);if(str[0]=='T'){op[i]=1;a[j++]=opn[i];}else if(str[0]=='Q'){op[i]=2;a[j++]=opn[i];}else op[i]=3;}sort(a+1,a+j);a[0]=0;for(i=k=1;i<j;i++){if(a[i]!=a[i-1]){if(a[i]-a[i-1]>1){s[k]=a[i-1]+1;e[k]=a[i]-1;k++;}s[k]=a[i];e[k]=a[i];k++;}}if(a[j-1]!=n){s[k]=a[j-1]+1;e[k]=n;}else k--;n=k;init();for(i=1;i<=m;i++){if(op[i]==1){k=lower_bound(s+1,s+n+1,opn[i])-s;k=idx[k];splay(k,0);remove();splay(getkth(root,1),0);splay(getkth(root,2),root);insert(k);}else if(op[i]==2){k=lower_bound(s+1,s+n+1,opn[i])-s;k=idx[k];splay(k,0);printf("%d\n",sum[L(root)]+1);}else if(op[i]==3){k=getkperson(root,opn[i]);printf("%d\n",k);}}}}return 0;
}
这篇关于HDU 3436 Queue-jumpers的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!