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]); }}

上一篇：打開攝像頭

下一篇：文件上傳一