題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)序列，初始時(shí)是亂序的，要求根據(jù)規(guī)則排序，規(guī)則是，遍歷每一個(gè)點(diǎn) i ，使得區(qū)間 [ i , a[ i ] ] 內(nèi)的數(shù)翻轉(zhuǎn)，a[ i ] 表示的是數(shù)列中第 i 大的數(shù)，可以看出每次翻轉(zhuǎn)都會(huì)使得第 i 大的數(shù)字到達(dá)第 i 個(gè)位置上去，題目要求輸出每次第 i 大的數(shù)的位置

題目分析：一個(gè)題拖了好久。。說(shuō)白了還是太懶了，一道比較經(jīng)典的伸展樹(shù)進(jìn)階題，做完之后還是收獲了不少東西的，首先分析題意，因?yàn)槊看畏D(zhuǎn)之后，第 i 個(gè)數(shù)在后續(xù)就沒(méi)有任何作用了，所以每次我們可以直接在翻轉(zhuǎn)后刪掉第 i 個(gè)數(shù)，而且初始時(shí)給出的數(shù)值我們可以轉(zhuǎn)換為相對(duì)大小，我們需要的只是其相對(duì)位置，所以可以排序，這樣就可以獲得相對(duì)位置了，也就是第 i 大的數(shù)的初始下標(biāo)編號(hào)，從而在建樹(shù)的時(shí)候，我們可以直接按照區(qū)間的下標(biāo)建樹(shù)，這樣做的好處是，在splay中編號(hào)為 i 的結(jié)點(diǎn)對(duì)應(yīng)的值就是 i ，方便后續(xù)的修改等操作，對(duì)于每一次操作，每次把第 i 個(gè)位置下標(biāo)的結(jié)點(diǎn)旋轉(zhuǎn)到根，我們就可以直接將結(jié)點(diǎn) i 旋轉(zhuǎn)到根，每次操作后splay的中序遍歷就是當(dāng)前維護(hù)的數(shù)列了（其實(shí)每個(gè) a[ i ] 在這里是第 i 大的數(shù)的位置，可能有點(diǎn)繞，但盡量去理解吧），因?yàn)槲覀冞@個(gè)題目主要是圍繞著相對(duì)大小展開(kāi)的，所以答案也就取決于當(dāng)前 a[ i ] 左邊有多少個(gè)數(shù)字，也就是?i + sum[ ch[ root ][ 0 ] ] 了，注意這里是 a[ i ] 左邊有多少個(gè)數(shù)字在 a[ i ] 的左邊，而不是比 a[ i ] 小的有多少個(gè)數(shù)字，這里一定要理解，因?yàn)榉D(zhuǎn)之后區(qū)間的絕對(duì)大小關(guān)系是比較混亂的，但是相對(duì)大小關(guān)系是比較明確的，查詢完后記得翻轉(zhuǎn)+刪除

到這里可能只是知道了如何解決這個(gè)題，下面的實(shí)現(xiàn)才是真正的難點(diǎn)，簡(jiǎn)單總結(jié)一下這個(gè)題目需要讓我們完成的操作就是，循環(huán)?n 次，每次找到第 i 大的數(shù)，輸出 i + sum[ ch[ root ][ 0 ] ] ，翻轉(zhuǎn)根的左子樹(shù)，刪除根

首先找到第 i 大的數(shù)并不難，因?yàn)槲覀兩鲜龅南鄬?duì)關(guān)系的轉(zhuǎn)換，第 i 大的數(shù)，其位置也就是我們排序后獲得的 pos 了，這里如果不懂先看代碼理解一下吧，總之就是可以直接獲得 pos 的位置，不需要再用find或rank函數(shù)尋找，其次直接輸出答案，而對(duì)于翻轉(zhuǎn)而言，因?yàn)橹霸诼骞茸龅哪莻€(gè)文藝平衡樹(shù)，是對(duì)于 m 次翻轉(zhuǎn)后，一次更新得到答案，那個(gè)題對(duì)于pushdown的要求比較低，隨便水水就過(guò)去了，但這個(gè)題不一樣，這個(gè)題對(duì)于每一次操作，都必須要實(shí)時(shí)更新，不能拖到最后一次更新，這就意味著每次向上rotate或向下find時(shí)，都必須要時(shí)刻跟著pushdown，不然會(huì)因?yàn)闆](méi)有及時(shí)更新導(dǎo)致答案錯(cuò)誤，對(duì)于pushdown的位置，我暫且是先記住的：

rotate里pushdown兩次

splay里pushdown三次

find/rank里每一層都要pushdown

find/rank里的pushdown并不難想，因?yàn)橄蛳伦吣敲纯隙ǖ胮ushdown啊，但splay和rotate里的pushdown我還沒(méi)琢磨清楚，先背過(guò)吧，而對(duì)于根的刪除，也是有技巧的，我們分為兩種情況：

根有左子樹(shù)，此時(shí)我們需要找到一個(gè)節(jié)點(diǎn)來(lái)代替根才行，可以選擇去右子樹(shù)中，找到一個(gè)最大的值，也就是排rank1的一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)一定沒(méi)有左兒子，直接將這個(gè)節(jié)點(diǎn)的左兒子與根節(jié)點(diǎn)的左兒子建立關(guān)系就好了

根沒(méi)有左子樹(shù)，這個(gè)簡(jiǎn)單，直接將根節(jié)點(diǎn)重置為根的右兒子就好了

當(dāng)然，上述操作對(duì)于右子樹(shù)同樣成立，看個(gè)人喜好吧

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;class Splay//存儲(chǔ)規(guī)則：小左大右，重復(fù)節(jié)點(diǎn)記錄 {#define root e[0].ch[1] //該樹(shù)的根節(jié)點(diǎn)private:class node{public:int lazy;int v,father;//節(jié)點(diǎn)值，父級(jí)節(jié)點(diǎn) int ch[2];//左孩子=0，右孩子=1int sum;//自己+自己下級(jí)有多少節(jié)點(diǎn)。在根節(jié)點(diǎn)為1。int recy;//記錄自己被重復(fù)了幾次};node e[N];//Splay樹(shù)主體int n,points;//使用存儲(chǔ)數(shù),元素?cái)?shù)void update(int x){e[x].sum=e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].recy;}int identify(int x){return e[e[x].father].ch[0]==x?0:1;}void connect(int x,int f,int son)//連接函數(shù)。用法：connect(son,father,1/0){e[x].father=f;e[f].ch[son]=x;}//作用：使得x的father=f，f的son=x.void rotate(int x){int y=e[x].father;pushdown(y);pushdown(x);int mroot=e[y].father;int mrootson=identify(y);int yson=identify(x);int B=e[x].ch[yson^1];connect(B,y,yson);connect(y,x,(yson^1));connect(x,mroot,mrootson);update(y);update(x);}void splay(int at,int to)//將at位置的節(jié)點(diǎn)移動(dòng)到to位置{pushdown(at);to=e[to].father;while(e[at].father!=to){int up=e[at].father;int ff=e[up].father;pushdown(ff);pushdown(up);pushdown(at);if(e[up].father==to) rotate(at);else if(identify(up)==identify(at)){rotate(up);rotate(at);}else{rotate(at);rotate(at);}}}int crepoint(int v,int father){n++;e[n].lazy=0;e[n].v=v;e[n].father=father;e[n].sum=e[n].recy=1;e[n].ch[0]=e[n].ch[1]=0;return n;}void destroy(int x)//pop后摧毀節(jié)點(diǎn) {e[x].v=e[x].ch[0]=e[x].ch[1]=e[x].sum=e[x].father=e[x].recy=0;if(x==n) n--;//最大限度優(yōu)化}public:void init(){points=n=root=0;e[root].v=e[root].father=e[root].sum=e[root].recy=e[root].ch[0]=e[root].ch[1]=0;}int getroot(){return root;}int find(int v)//用于外部的find調(diào)用{int now=root;while(true){if(e[now].v==v){splay(now,root);return now;}int next=v<e[now].v?0:1;if(!e[now].ch[next]) return 0;now=e[now].ch[next];}}int build(int v)//內(nèi)部調(diào)用的插入函數(shù)，沒(méi)有splay {points++;if(points==1)//特判無(wú)點(diǎn)狀態(tài) {root=n+1;crepoint(v,0);}else{int now=root;while(true)//向下找到一個(gè)空節(jié)點(diǎn) {e[now].sum++;//自己的下級(jí)肯定增加了一個(gè)節(jié)點(diǎn) if(v==e[now].v){e[now].recy++;return now;}int next=v<e[now].v?0:1;if(!e[now].ch[next]){crepoint(v,now);e[now].ch[next]=n;return n;}now=e[now].ch[next];}}return 0;}void push(int v)//插入元素時(shí)，先添加節(jié)點(diǎn)，再進(jìn)行伸展 {int add=build(v);splay(add,root);}void pop(int v)//刪除節(jié)點(diǎn) {int deal=find(v);if(!deal) return;points--;if(e[deal].recy>1){e[deal].recy--;e[deal].sum--;return;}if(!e[deal].ch[0]){root=e[deal].ch[1];e[root].father=0;}else{int lef=e[deal].ch[0];while(e[lef].ch[1]) lef=e[lef].ch[1];splay(lef,e[deal].ch[0]);int rig=e[deal].ch[1];connect(rig,lef,1);connect(lef,0,1);update(lef);}destroy(deal);}int rank(int v)//獲取值為v的元素在這棵樹(shù)里是第幾小 {int ans=0,now=root;while(true){if(e[now].v==v) {ans+=e[e[now].ch[0]].sum;splay(now,root);return ans+1;}if(now==0) return 0;if(v<e[now].v) now=e[now].ch[0];else{ans=ans+e[e[now].ch[0]].sum+e[now].recy;now=e[now].ch[1];}}return 0;}int atrank(int x,int rt)//獲取第x小的元素的值 {if(x>points) return -inf;int now=rt;while(true){pushdown(now);int minused=e[now].sum-e[e[now].ch[1]].sum;if(x>e[e[now].ch[0]].sum&&x<=minused) break;if(x<minused) now=e[now].ch[0];else{x=x-minused;now=e[now].ch[1];}}splay(now,root);return e[now].v;}int upper(int v)//尋找該值對(duì)應(yīng)的一個(gè)最近的上界值 {int now=root;int result=inf;while(now){if(e[now].v>=v&&e[now].v<result) result=e[now].v;if(v<e[now].v) now=e[now].ch[0];else now=e[now].ch[1];}return result;}int lower(int v)//尋找該值對(duì)應(yīng)的一個(gè)最近的下界值 {int now=root;int result=-inf;while(now){if(e[now].v<=v&&e[now].v>result) result=e[now].v;if(v>e[now].v) now=e[now].ch[1];else now=e[now].ch[0];}return result;}void reverse(int pos,int i){splay(pos,root);//把第pos小的點(diǎn)旋到根e[e[root].ch[0]].lazy^=1;printf("%d ",i+e[e[root].ch[0]].sum);remove();}void pushdown(int k){if(k&&e[k].lazy){swap(e[k].ch[0],e[k].ch[1]);e[e[k].ch[0]].lazy^=1;e[e[k].ch[1]].lazy^=1;e[k].lazy=0;}}void remove(){int t=root;if(e[root].ch[1]){atrank(1,e[root].ch[1]);e[root].ch[0]=e[t].ch[0];if(e[t].ch[0]) e[e[t].ch[0]].father=root;}elseroot=e[root].ch[0];e[root].father=0;update(root);}#undef root }tree;struct Node {int pos,val;bool operator<(const Node& a)const{if(val!=a.val)return val<a.val;return pos<a.pos;} }a[N];int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;while(scanf("%d",&n)!=EOF&&n){tree.init();for(int i=1;i<=n;i++){scanf("%d",&a[i].val);tree.push(i);a[i].pos=i;}sort(a+1,a+1+n);for(int i=1;i<n;i++){int pos=a[i].pos;tree.reverse(pos,i);}printf("%d\n",n);}return 0; }

?

超強(qiáng)干貨來(lái)襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的HDU - 1890 Robotic Sort(Splay-区间翻转+删除根节点)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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