CQOI2014 排序机械臂--splay膜版题

2019-11-08 18:21:15

字体：大中小

来源：转载

供稿：网友

【CQOI2014】排序机械臂

Time Limit:20000MS Memory Limit:565536K Case Time Limit:2000MS

Description

为了把工厂中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到最低的物品位置P1，并把从左起第1个至第P1个之间的物品反序；第二次找到第二低的物品的位置P2，并把左起第二个至第P2个之间的物品反序……最终所有的物品都会被排好序。这里写图片描述上图给出一个示例，第一次操作前，最低物品在位置4，于是把第1至第4个物品反序；第二次操作前，第二低的物品在位置6，于是把第2至第6的物品反序…… 你的任务是编写一个程序，确定操作序列，即每次操作前第i低的物品所在的位置Pi，以便机械臂工作。需要注意的是，如果有高度相同的物品，必须保证排序后他们的相对位置关系与初始时相同。

Input

第一行包含一个正整数n，表示需要排序的物品数量。第二行包含n和空格分隔的整数ai，表示每个物品的高度。

Output

输出一行包含n个空格分隔的整数Pi。

Sample Input

样例输入1： 6 3 4 5 1 6 2

样例输入2 4 3 3 2 1 Sample Output

样例输出1： 4 6 4 5 6 6

样例输出2： 4 2 4 4 Hint

对于30%的数据，1<=n<=1000 对于100%的数据，1<=n<=100000,1<=ai<=2*10^9

splay，两个值得注意的地方。 1.询问一次删除最小的元素，反序即处理开头到某个位置，splay过后直接给左儿子打标记即可 2.编号已定，每次该找的节点编号可以进行预处理，splay上不用再带min进行冗余操作，对比如下（加min和不加min）这里写图片描述

#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<cstdlib>#include<queue>#include<vector>#include<cmath>using namespace std;template <typename T>inline void _read(T& x){ char ch=getchar();bool sign=true; while(!isdigit(ch)){if(ch=='-')sign=false;ch=getchar();} for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0'; if(!sign)x=-x;}int n,root;struct node{ int id,val; node(){} node(int x,int y){id=x;val=y;}};node a[100005];bool cmp1(node G,node H){ if(G.val==H.val)return G.id<H.id; else return G.val<H.val;}bool cmp2(node G,node H){ return G.id<H.id;}int father[100005],l[100005],r[100005],size[100005];int PRe[100005];bool rev[100005];void pushdown(int x){ if(rev[x]){ rev[x]^=1;rev[l[x]]^=1;rev[r[x]]^=1; swap(l[x],r[x]); }}bool isroot(int x){ return x!=l[father[x]]&&x!=r[father[x]];}void update(int x){ size[x]=size[l[x]]+size[r[x]]+1;}void zig(int x){ int y=father[x],z=father[y]; if(l[z]==y)l[z]=x; else if(r[z]==y)r[z]=x; father[y]=x; father[x]=z; father[r[x]]=y; l[y]=r[x]; r[x]=y; update(y);update(x);}void zag(int x){ int y=father[x],z=father[y]; if(l[z]==y)l[z]=x; else if(r[z]==y)r[z]=x; father[y]=x; father[x]=z; father[l[x]]=y; r[y]=l[x]; l[x]=y; update(y);update(x);}int q[100005];void splay(int x){ int i,j,k,top=0; q[++top]=x; for(i=x;!isroot(i);i=father[i])q[++top]=father[i]; while(top)pushdown(q[top--]); while(!isroot(x)){ int y=father[x],z=father[y]; if(!isroot(y)){ if(r[z]==y){ if(r[y]==x){zag(y);zag(x);} else {zig(x);zag(x);} } else { if(l[y]==x){zig(y);zig(x);} else {zag(x);zig(x);} } } else { if(l[y]==x)zig(x); else zag(x); } }}int getr(int x){ pushdown(x); while(r[x]){ x=r[x]; pushdown(x); } return x;}void del(int x){ splay(x); father[l[x]]=father[r[x]]=0; if(l[x]==0)root=r[x]; else { root=l[x]; int t=getr(l[x]); splay(t); father[t]=0;father[r[x]]=t;r[t]=r[x]; }}int main(){ int i,j,k; cin>>n; for(i=1;i<=n;i++){ _read(a[i].val); a[i].id=i; } sort(a+1,a+1+n,cmp1); for(i=1;i<=n;i++){ a[i].val=i; pre[i]=a[i].id; } root=1; for(i=1;i<n;i++){ father[i+1]=i; r[i]=i+1; size[i]=n+1-i; } father[n]=n-1; for(i=1;i<=n;i++){ splay(pre[i]); if(l[pre[i]])rev[l[pre[i]]]^=1; //cout<<size[l[pre[i]]]+i<<" "; printf("%d ",size[l[pre[i]]]+i); del(pre[i]); }}

上一篇：打开摄像头

下一篇：文件上传一