題目鏈接：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; }
?
