题目描述
达达在买回家的火车票,因为正值春运,售票处排起了长队。
因为晚上室内光线很暗,所以很多人趁机插队。
现在给每个人赋予一个整数作为编号,告诉你每一个排队的人的编号,和他进入队列时的具体位置。
请你确定最终的队列顺序。
样例
4
0 77
1 51
1 33
2 69
4
0 20523
1 19243
1 3890
0 31492
77 33 69 51
31492 20523 3890 19243
算法1
(Splay) 均摊$O(nlogn)$
我们发现,直接用$Splay$维护队列即可。维护$size$为这个点下方点的数目,通过$size$来$logn$找到该插入的位置。基本为模板(甚至连前驱后继都免了)
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
struct SPLAY{
int fa,ch[2],size,id;
}s[200100];
inline void pushup(int u){
s[u].size=s[s[u].ch[0]].size+s[s[u].ch[1]].size+1;
}
inline void rotate(int x){
int y=s[x].fa; int z=s[y].fa; int k=s[y].ch[1]==x;
s[z].ch[s[z].ch[1]==y]=x; s[x].fa=z;
s[y].ch[k]=s[x].ch[k^1]; s[s[x].ch[k^1]].fa=y;
s[x].ch[k^1]=y; s[y].fa=x;
pushup(y);pushup(x);
}
int ls=1,root;
inline void splay(int x,int goal){
int y,z;
while(s[x].fa!=goal){
y=s[x].fa;z=s[y].fa;
if(z!=goal)
(s[z].ch[1]==y)^(s[y].ch[1]==x)?rotate(x):rotate(y);
rotate(x);
}
if(!goal) root=x;
}
void ins(int x,int id){//插入
if(!root){
s[ls].fa=0;
s[ls].ch[0]=s[ls].ch[1]=0;
s[ls].size=1;
s[ls].id=id;
root=ls++;
return;
}
int u=root;
if(!x){
int fa=u;
while(u){
fa=u;
u=s[u].ch[0];
}
u=fa;
int t=s[u].ch[0];
s[u].ch[0]=ls;
s[ls].fa=u;
s[ls].ch[0]=t;s[ls].ch[1]=0;
s[ls].id=id;
s[t].fa=ls;
pushup(ls++);
}
else
while(x){
if(x<s[s[u].ch[0]].size){u=s[u].ch[0];continue;}
x-=s[s[u].ch[0]].size;
if(!x||x==1){
int k=(x==1);
int t=s[u].ch[k];
s[u].ch[k]=ls;
s[ls].fa=u;
s[ls].ch[k]=t;s[ls].ch[k^1]=0;
s[ls].id=id;
s[t].fa=ls;
pushup(ls++);
break;
}
x--;
u=s[u].ch[1];
}
splay(ls-1,0);
}
void opt(int u){//中序遍历输出顺序
if(s[u].ch[0]) opt(s[u].ch[0]);
printf("%d ",s[u].id);
if(s[u].ch[1]) opt(s[u].ch[1]);
}
int main(){
srand(19260817);
int n,p,v;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++){
scanf("%d%d",&p,&v);
ins(p,v);
if((i+1)%1000==0) splay(rand()%(ls-1)+1,0);//被最后一个点卡了,所以随机指定根来维护复杂度
}
opt(root);
printf("\n");
for(int i=0;i<=ls;i++)
s[i].fa=s[i].ch[0]=s[i].ch[1]=s[i].size=s[i].id=0;
ls=1;root=0;
}
return 0;
}
%%%%
杀xbj用yb刀