hdu 1890 Robotic SortI(splay區間旋轉操作)

 2023-12-25 阅读 47 评论 0

摘要:題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1890 ? 題解:splay又一高級的功能,區間旋轉這個是用線段樹這些實現不了的,這題可以學習splay的旋轉方法還有splay tree是按照中序來的,也就是說中序遍歷后會得到原序列所以建樹和

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1890

?

題解:splay又一高級的功能,區間旋轉這個是用線段樹這些實現不了的,這題可以學習splay的旋轉方法還有splay tree是按照中序來的,也就是說中序遍歷后會得到原序列所以建樹和線段樹差不多稍微有點不一樣。其實splay tree核心操作就是splay就是將某個點移到goal下面優化bst的操作。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1e5 + 10;
int pre[M] , ch[M][2] , size[M] , rev[M] , tot , root;//rev類似懶惰標記表示該區間是否要旋轉
void NewNode(int &r , int fa , int k) {r = k;pre[r] = fa;ch[r][0] = ch[r][1] = 0;size[r] = 1;rev[r] = 0;
}
void Rev(int r) {if(!r) return ;else {swap(ch[r][0] , ch[r][1]);rev[r] ^= 1;}
}//新的操作區間旋轉
void push_up(int r) {size[r] = size[ch[r][0]] + size[ch[r][1]] + 1;
}
void push_down(int r) {if(rev[r]) {Rev(ch[r][0]);Rev(ch[r][1]);rev[r] = 0;}
}//新操作的push_down;
void Rotate(int x , int kind) {int y = pre[x];push_down(y);push_down(x);ch[y][!kind] = ch[x][kind];pre[ch[x][kind]] = y;if(pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x;pre[x] = pre[y];ch[x][kind] = y;pre[y] = x;push_up(y);push_up(x);
}
void Splay(int r , int goal) {push_down(r);while(pre[r] != goal) {if(pre[pre[r]] == goal) {push_down(r);push_down(pre[r]);Rotate(r , ch[pre[r]][0] == r);}else  {push_down(r);push_down(pre[r]);push_down(pre[pre[r]]);int y = pre[r];int kind = (ch[pre[y]][0] == y);if(ch[y][kind] == y) {Rotate(r , !kind);Rotate(r , kind);}else {Rotate(y , kind);Rotate(r , kind);}}}push_up(r);if(goal == 0) root = r;
}//有新的操作之后注意稍微修改一下旋轉操作
int get_Max(int r) {push_down(r);while(ch[r][1]) {r = ch[r][1];push_down(r);}push_up(r);return r;
}
void Remove() {if(!ch[root][0]) {root = ch[root][1];pre[root] = 0;push_up(root);}else {int Max_point = get_Max(ch[root][0]);Splay(Max_point , root);ch[Max_point][1] = ch[root][1];pre[ch[root][1]] = Max_point;root = Max_point;pre[root] = 0;push_up(root);}
}//新的remove操作刪除節點。
void build(int l , int r , int &x , int fa) {if(l > r) return ;int mid = (l + r) >> 1;NewNode(x , fa , mid);build(l , mid - 1 , ch[x][0] , x);build(mid + 1 , r , ch[x][1] , x);push_up(x);
}
struct TnT {int pos , val;
}a[M << 1];
bool cmp(TnT x , TnT y) {if(x.val == y.val) return x.pos < y.pos;return x.val < y.val;
}
int main() {int n;while(scanf("%d" , &n) , n) {for(int i = 0 ; i < n ; i++) {scanf("%d" , &a[i].val);a[i].pos = i + 1;}sort(a , a + n , cmp);root = tot = 0;pre[root] = ch[root][1] = ch[root][0] = size[root] = rev[root] = 0;build(1 , n , root , 0);for(int i = 0 ; i < n - 1 ; i++) {Splay(a[i].pos , 0);Rev(ch[root][0]);printf("%d " , size[ch[root][0]] + i + 1);Remove();}printf("%d\n" , n);}return 0;
}

?

轉載于:https://www.cnblogs.com/TnT2333333/p/7204188.html

版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接:https://hbdhgg.com/1/195014.html

发表评论:

本站为非赢利网站,部分文章来源或改编自互联网及其他公众平台,主要目的在于分享信息,版权归原作者所有,内容仅供读者参考,如有侵权请联系我们删除!

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息