首页 > 代码库 > UVA 11922 Permutation Transformer —— splay伸展树
UVA 11922 Permutation Transformer —— splay伸展树
题意:根据m条指令改变排列1 2 3 4 … n ,每条指令(a, b)表示取出第a~b个元素,反转后添加到排列尾部
分析:用一个可分裂合并的序列来表示整个序列,截取一段可以用两次分裂一次合并实现,粘贴到末尾可以用一次合并实现。
翻转可以采用在每个结点上做标记的方法,flip = 1意味着将这棵子树翻转,可以类似线段树用一个pushdown()实现标记向下传递。
可以发现当前排列就是伸展树的中序遍历序列。中序遍历打印结果即可。
注意代码中设置了虚拟首结点0的技巧。
代码如下:
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 7 struct Node { 8 Node* ch[2]; 9 int r, v, s; 10 int flip; 11 Node(int vv): v(vv) { 12 r = rand(); 13 s = 1; 14 ch[0] = ch[1] = NULL; 15 flip = 0; 16 } 17 bool cmp(const int &x) const { 18 if(x == v) return -1; 19 return x < v ? 0 : 1; 20 } 21 void maintain() { 22 s = 1; 23 if(ch[0] != NULL) s += ch[0]->s; 24 if(ch[1] != NULL) s += ch[1]->s; 25 } 26 void pushdown() { 27 if(flip) { 28 flip = 0; 29 swap(ch[0], ch[1]); 30 if(ch[0] != NULL) ch[0]->flip = !ch[0]->flip; 31 if(ch[1] != NULL) ch[1]->flip = !ch[1]->flip; 32 } 33 } 34 }; 35 void rotate(Node* &o, int d) { 36 Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; 37 o->maintain(); k->maintain(); o = k; 38 } 39 void insert(Node* &o, int x) { 40 if(o == NULL) o = new Node(x); 41 else { 42 int d = o->cmp(x); 43 insert(o->ch[d], x); 44 if(o->ch[d]->r > o->r) rotate(o, d^1); 45 } 46 o->maintain(); 47 } 48 49 void splay(Node* &o, int k) { 50 o->pushdown(); 51 int s = o->ch[0] == NULL ? 0 : o->ch[0]->s; 52 int d = k <= s ? 0 : (k == s+1 ? -1 : 1); 53 if(d == 1) k -= s+1; 54 if(d != -1) { 55 splay(o->ch[d], k); 56 rotate(o, d^1); 57 } 58 } 59 60 Node* merge(Node* left, Node* right) { 61 splay(left, left->s); 62 left->ch[1] = right; 63 left->maintain(); 64 return left; 65 } 66 67 void split(Node* o, int k , Node* &left, Node* &right) { 68 splay(o, k); 69 left = o; 70 right = o->ch[1]; 71 o->ch[1] = NULL; 72 left->maintain(); 73 } 74 vector<int> seq; 75 void dfs(Node* o) { 76 if(o == NULL) return; 77 o->pushdown(); 78 dfs(o->ch[0]); 79 if(o->v) { 80 //printf("%d ", o->v); 81 seq.push_back(o->v); 82 } 83 dfs(o->ch[1]); 84 } 85 int n, m; 86 int main() { 87 cin >> n >> m; 88 Node* root = new Node(0); //虚拟首结点0,方便分裂操作 89 for(int i = 1; i <= n; i++) insert(root, i); 90 while(m--) { 91 int a, b; 92 cin >> a >> b; 93 Node *left, *mid, *right, *o; 94 split(root, a, left, o); 95 split(o, b-a+1, mid, right); 96 mid->flip ^= 1; 97 root = merge(merge(left, right), mid); 98 } 99 dfs(root); 100 for(int i = 0; i < seq.size(); i++) cout<<seq[i]<<endl; 101 return 0; 102 }
UVA 11922 Permutation Transformer —— splay伸展树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。