AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1552

【分析】

　　這題哇！又有翻轉操作...每次要輸出第幾個？是吧...

　　所以又要用Splay了。

　　可是這道題有創(chuàng)新的地方，因為又有數(shù)值上的有序[取最小值]，又有位置上的有序[翻轉和求第幾個]

　　可是畢竟最小值的操作會簡單很多...所以我們采用的是將位置作為Splay的節(jié)點信息。

　　那么怎么快速得到最小值的位置呢？當然就是常用的push_up了...向上更新就好了。

　　這里一定要注意題目所說：按照剛開始給你的順序排序，在實現(xiàn)中就是數(shù)組的下標了，每次還需要比較兩邊最優(yōu)值的大小和下標。

　　然后每次選出最小值，將其轉到樹根，輸出其左子樹的大小＋已經(jīng)刪去的最小值數(shù)目，然后將它刪去，從左子樹中選一個最右邊的節(jié)點翻到頂上，作為新的節(jié)點。

　　大致過程就是這樣啦...【表示都是筆者想出來的...很開心啊...只是速度還是沒有某人快啊...】

　　

#include<cstdio> #include<cstring> #include<algorithm>using namespace std;inline int in(){int x=0,f=1;char ch=getchar();while((ch>'9' || ch<'0') && ch!='-') ch=getchar();if(ch=='-') f=-1,ch=getchar();while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f; }const int maxn=100010; const int INF=0x7f7f7f7f;struct Node{int ch[2],f;int sz,mn,lc,dt;bool rv; }s[maxn];int n,rt; int a[maxn];void push_down(int x){if(s[x].rv){swap(s[x].ch[0],s[x].ch[1]);s[s[x].ch[0]].rv^=1,s[s[x].ch[1]].rv^=1;s[x].rv=0;} } void update(int x){s[x].sz=s[s[x].ch[0]].sz+s[s[x].ch[1]].sz+1;s[x].mn=s[x].dt,s[x].lc=x;int l,r;l=s[x].ch[0],r=s[x].ch[1];if((s[l].mn<s[x].mn) || (s[l].mn==s[x].mn && s[l].lc<s[x].lc)) s[x].mn=s[l].mn,s[x].lc=s[l].lc;if((s[r].mn<s[x].mn) || (s[r].mn==s[x].mn && s[r].lc<s[x].lc)) s[x].mn=s[r].mn,s[x].lc=s[r].lc; }int build(int l,int r){if(l>r) return 0;int mid=(l+r)>>1;s[mid].ch[0]=build(l,mid-1);s[mid].ch[1]=build(mid+1,r);if(s[mid].ch[0]) s[s[mid].ch[0]].f=mid;if(s[mid].ch[1]) s[s[mid].ch[1]].f=mid;s[mid].dt=a[mid];update(mid);return mid; }void Rotate(int x,int k){int y=s[x].f;s[x].f=s[y].f;if(s[y].f) s[s[y].f].ch[y==s[s[y].f].ch[1]]=x;s[y].ch[k]=s[x].ch[k^1];if(s[x].ch[k^1]) s[s[x].ch[k^1]].f=y;s[y].f=x,s[x].ch[k^1]=y;update(y),update(x); }void Splay(int x,int gf){int y;while(s[x].f!=gf){y=s[x].f;if(s[y].f==gf) Rotate(x,x==s[y].ch[1]);else{int z=s[y].f;if(y==s[z].ch[0]){if(x==s[y].ch[0]) Rotate(y,0),Rotate(x,0);else Rotate(x,1),Rotate(x,0);}else{if(x==s[y].ch[1]) Rotate(y,1),Rotate(x,1);else Rotate(x,0),Rotate(x,1);}}}if(!gf) rt=x; }int Find_right(int x){int p=x,f=-1;while(p){push_down(p);f=p;p=s[f].ch[1];}return f; }int st[maxn],tp;void up_push_down(int x){int p=x;while(p)st[++tp]=p,p=s[p].f;while(tp)push_down(st[tp--]); }int main(){ #ifndef ONLINE_JUDGEfreopen("1552.in","r",stdin);freopen("1552.out","w",stdout); #endifn=in();for(int i=1;i<=n;i++) a[i]=in();s[0].mn=INF;s[0].lc=-1;rt=build(1,n);int x;for(int i=1;i<=n;i++){up_push_down(s[rt].lc);Splay(s[rt].lc,0);printf("%d",s[s[rt].ch[0]].sz+i);if(i!=n) printf(" ");s[s[rt].ch[0]].rv^=1;if(!s[rt].ch[0]){s[s[rt].ch[1]].f=0;rt=s[rt].ch[1];}else{x=Find_right(s[rt].ch[0]);Splay(x,rt);s[x].f=0;s[x].ch[1]=s[rt].ch[1];if(s[rt].ch[1])s[s[rt].ch[1]].f=x;update(x);rt=x;}}return 0; } View Code

?

轉載于:https://www.cnblogs.com/Robert-Yuan/p/5087213.html

總結

以上是生活随笔為你收集整理的BZOJ 1552/1506 [Cerc2007]robotic sort的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。