來自FallDream的博客，未經允許，請勿轉載，謝謝。

---

H 國是一個熱愛寫代碼的國家，那里的人們很小去學校學習寫各種各樣的數據結構。伸展樹（splay）是一種數據結構，因為代碼好寫，功能多，效率高，掌握這種數據結構成為了 H 國的必修技能。有一天，邪惡的“卡”帶著他的邪惡的“常數”來企圖毀滅 H 國。“卡”給 H 國的人洗腦說，splay 如果寫成單旋的，將會更快。“卡”稱“單旋 splay”為“spaly”。雖說他說的很沒道理，但還是有 H 國的人相信了，小 H 就是其中之一，spaly 馬上成為他的信仰。 而 H 國的國王，自然不允許這樣的風氣蔓延，國王構造了一組數據，數據由 m 個操作構成，他知道這樣的數據肯定打垮 spaly，但是國王還有很多很多其他的事情要做，所以統計每個操作所需要的實際代價的任務就交給你啦。 數據中的操作分為五種： 1. 插入操作：向當前非空 spaly 中插入一個關鍵碼為 key 的新孤立節點。插入方法為，先讓 key 和根比較，如果?key 比根小，則往左子樹走，否則往右子樹走，如此反復，直到某個時刻，key 比當前子樹根 x 小，而 x 的左子樹為空，那就讓 key 成為 x 的左孩子； 或者 key 比當前子樹根 x 大，而 x 的右子樹為空，那就讓 key 成為? x 的右孩子。該操作的代價為：插入后，key 的深度。特別地，若樹為空，則直接讓新節點成為一個單個節點的樹。（各節點關鍵碼互不相等。對于“深度”的解釋見末尾對 spaly 的描述）。 2. 單旋最小值：將 spaly 中關鍵碼最小的元素 xmin 單旋到根。操作代價為：單旋前 xmin 的深度。（對于單旋操作的解釋見末尾對 spaly 的描述）。 3. 單旋最大值：將 spaly 中關鍵碼最大的元素 xmax 單旋到根。操作代價為：單旋前 xmax 的深度。 4. 單旋刪除最小值：先執行 2 號操作,然后把根刪除。由于 2 號操作之后,根沒有左子樹,所以直接切斷根和右子樹的聯系即可（具體見樣例解釋）。 操作代價同 2 號操 作。 5. 單旋刪除最大值：先執行 3 號操作,然后把根刪除。 操作代價同 3 號操作。 對于不是 H 國的人，你可能需要了解一些 spaly 的知識，才能完成國王的任務： a. spaly 是一棵二叉樹，滿足對于任意一個節點 x，它如果有左孩子 lx，那么 lx 的關鍵碼小于 x 的關鍵碼。如果有右孩子 rx，那么 rx 的關鍵碼大于 x 的關鍵碼。 b. 一個節點在 spaly 的深度定義為：從根節點到該節點的路徑上一共有多少個節點（包括自己）。 c. 單旋操作是對于一棵樹上的節點 x 來說的。一開始,設 f 為 x 在樹上的父親。如果 x 為 f 的左孩子，那么執行 zig(x) 操作（如上圖中，左邊的樹經過 zig(x) 變為了右邊的樹），否則執行 zag(x) 操作（在上圖中，將右邊的樹經過 zag(f) 就變成了左邊的樹）。每當執 行一次 zig(x) 或者 zag(x)，x 的深度減小 1，如此反復， 直到 x 為根。總之，單旋 x 就是通過反復執行 zig 和 zag 將 x 變為根 m<=10^5 很牛逼的一道題233? 只有傻瓜才會寫一個spaly去模擬這些操作。 因為這道題只對最值進行操作，所以每次操作全是左旋或者全是右旋 發現把最小值轉上去的時候，它的右子樹深度不變，其他點深度+1，然后最小值深度變為1 轉最大值同理 插入的時候只可能插在前驅右兒子或者后繼左兒子。實際上它們只有一個位置是空的，判斷插入到哪個即可。 這個明顯可以維護。只需要支持區間加，求出最長的大于某一深度的區間，插入一個點，查詢前驅后繼等操作即可。 因為本題可以離線，所以直接線段樹就好了。 當然，既然是一道關于spaly的題，你也可以用splay直接維護哦 ?復雜度nlogn #include<iostream> #include<cstdio> #define getchar() (*S++) char B[1<<26],*S=B; #define INF 2000000000 #define MN 100000 using namespace std; inline int read() {int x = 0; char ch = getchar();while(ch < '0' || ch > '9')ch = getchar();while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x; }int n,fa[MN+5],val[MN+5],cnt=0,c[MN+5][2],rt=0,Q,s[MN+5],dep[MN+5],mn[MN+5],size[MN+5];inline void pushdown(int x) {int l=c[x][0],r=c[x][1];val[l]+=val[x];dep[l]+=val[x];mn[l]+=val[x];val[r]+=val[x];dep[r]+=val[x];mn[r]+=val[x];val[x]=0; }inline void update(int x) {int l=c[x][0],r=c[x][1];size[x]=size[l]+size[r]+1;mn[x]=dep[x];if(l) mn[x]=min(mn[x],mn[l]);if(r) mn[x]=min(mn[x],mn[r]); }void rotate(int x,int&k) {int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;if(y==k) k=x; else c[z][c[z][1]==y]=x;fa[x]=z;fa[y]=x;fa[c[x][r]]=y;c[y][l]=c[x][r];c[x][r]=y;update(y);update(x); }void splay(int x,int&k) {for(;x!=k;rotate(x,k))if(fa[x]!=k) rotate((c[fa[fa[x]]][1]==fa[x]^c[fa[x]][1]==x)?x:fa[x],k); }void ins(int&x,int S,int d,int last) {if(!x){x=++cnt;s[cnt]=S;dep[cnt]=mn[cnt]=d;size[cnt]=1;fa[cnt]=last;return;}ins(c[x][S>s[x]],S,d,x);update(x); }int Find_Before(int x,int S) {if(!x) return 0;if(val[x]) pushdown(x);if(s[x]>S) return Find_Before(c[x][0],S);return (Q=Find_Before(c[x][1],S))?Q:x; }int Find_After(int x,int S) {if(!x) return 0;if(val[x]) pushdown(x);if(s[x]<S) return Find_After(c[x][1],S);return (Q=Find_After(c[x][0],S))?Q:x; }int Find(int x,int rk) {if(val[x]) pushdown(x);int sz=size[c[x][0]]+1;if(sz==rk) return x;if(sz<rk) return Find(c[x][1],rk-sz);return Find(c[x][0],rk); }int FindLeft(int x,int d) {if(!x) return 0;if(val[x]) pushdown(x);if(min(mn[c[x][0]],dep[x])>=d) return FindLeft(c[x][1],d)+size[c[x][0]]+1;else return FindLeft(c[x][0],d); }int FindRight(int x,int d) {if(!x) return 0;if(val[x]) pushdown(x);if(min(mn[c[x][1]],dep[x])>=d) return FindRight(c[x][0],d)+size[c[x][1]]+1;else return FindRight(c[x][1],d); }inline int Split(int l,int r) {int Lt=Find(rt,l-1),Rt=Find(rt,r+1);splay(Lt,rt);splay(Rt,c[rt][1]);return c[c[rt][1]][0]; }inline void Modify(int l,int r,int ad) {int y=Split(l,r);val[y]+=ad;mn[y]+=ad;dep[y]+=ad; }void change(int x,int S) {if(val[x]) pushdown(x);if(s[x]==S) dep[x]=1;else change(c[x][S>s[x]],S);update(x); }int main() {fread(B,1,1<<26,stdin);n=read();ins(rt,-INF,INF,0);ins(rt,INF,INF,0);mn[0]=INF;for(int i=1;i<=n;++i){int op=read();if(op==1){int x=read(),bef=Find_Before(rt,x),aft=Find_After(rt,x);int D=max(bef>2?dep[bef]:0,aft>2?dep[aft]:0)+1;ins(rt,x,D,0);splay(cnt,rt);printf("%d\n",D);}if(!(op&1)){int x=Find(rt,2),y=min(FindLeft(rt,dep[x]),size[rt]-1)-1;printf("%d\n",dep[x]);Modify(2,size[rt]-1,1);if(y>1) Modify(2,y+1,-1);change(rt,s[x]);}if((op&1)&&op>1){int x=Find(rt,size[rt]-1),y=min(FindRight(rt,dep[x]),size[rt]-1)-1;printf("%d\n",dep[x]);Modify(2,size[rt]-1,1);if(y>1) Modify(size[rt]-y,size[rt]-1,-1);change(rt,s[x]);}if(op>=4){if(op==4) splay(Find(rt,2),rt);else splay(Find(rt,size[rt]-1),rt);int l=(op==5),r=l^1,y=c[rt][l];c[y][r]=c[rt][r];fa[y]=0;fa[c[rt][r]]=y;rt=y;val[rt]-=1;update(rt);}}return 0; }

轉載于:https://www.cnblogs.com/FallDream/p/bzoj4825.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的[bzoj4825]:[Hnoi2017]单旋的全部內容，希望文章能夠幫你解決所遇到的問題。

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