首页 > 代码库 > BZOJ 3223 Tyvj 1729 文艺平衡树
BZOJ 3223 Tyvj 1729 文艺平衡树
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
Input
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
Output
输出一行n个数字，表示原始序列经过m次变换后的结果
Sample Input
5 3
1 3
1 3
1 4
1 3
1 3
1 4
Sample Output
4 3 2 1 5
HINT
N,M<=100000
为了调出一个正常的splay，实在是调了太久太久。
不过至少调出来了嘛！?
就是最普通的平衡树，而且此题还不用insert和remove。所以，就是build，splay，merge和split，再加上rev标记和pushdown。splay的cmp与treap的cmp不同，treap的cmp是按值的，而splay是按siz的（因为是下标标号）。所以说，insert的时候有k还有x（x似乎无用）。额，似乎很显然。而进入ch[1]的时候，一定不能忘了先把k减下去。
关于splay操作，按理是双旋的，但我写了随机比较单旋和双旋，似乎没有什么大区别。事实似乎也是这样。
| splay单旋 | 2776 kb | 2184 ms | 2351 B |
| splay双旋 | 2776 kb | 2004 ms | 2559 B |
但是，确实有理论证明。双旋可以有效地“本质化地”优化树的形态。
关于split和merge，刘汝佳建议，使用虚拟节点，但本人嫌麻烦，只需要再特判一下。因为split是把树o的前k个分入left，之后的分入right，当k为0时就不用旋也不能旋了。而且merge是把left变成“右空树”再连上 right，当left为null时就不用旋也不能旋了。第一次感觉null这么方便。
而rev标记，是只要访问就该pushdown了，无论是insert，remove，还是splay，print，如果忘了会出大事。
而maintain（update）呢？只要树形态变化就应该做。也就是build，insert，remove，rotate，还有merge和split。注意splay内部并不需要maintain，因为splay本身不过是一堆rotate。而remove时，maintain需要注意判断null，不然一旦乱搞，这棵树就完了。而null时，一般都是o->ch[0]==null&&o->ch[1]==null，在d==-1时if(o->ch[0]==null) o=o->ch[1];这样是很明显的。
我们在进行区间操作时，一般都会把操作的区间split出来，防止其他元素纠结，之后在merge回去。此题无需关心insert，但是如果有insert，插入之后还应splay一下，只有这样才能摆脱链的诅咒。
第一次敲splay，真的很苦啊。
1 /************************************************************** 2 Problem: 3223 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:2184 ms 7 Memory:2776 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 const int N = 100010;13 struct Node {14 int val, siz;15 bool rev;16 Node *ch[2];17 int cmp(int k) {18 if(k<=ch[0]->siz) return 0;19 if(k<=ch[0]->siz+1) return -1;20 return 1;21 }22 void pushdown() {if(rev) {23 std::swap(ch[0],ch[1]);24 ch[0]->rev^=1;25 ch[1]->rev^=1;26 rev = 0; 27 }}28 void maintain() {29 siz=ch[0]->siz+ch[1]->siz+1;30 }31 }pool[N], *tail=pool, *null=pool, *root;32 //int aa[N];33 void rotate(Node *&o,int d) {34 Node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;35 o->maintain();k->maintain();o=k;36 }37 Node *build(int lf,int rg) {38 Node *o=++tail;39 int mid=(lf+rg)>>1;40 o->val=mid;//aa[mid];41 o->ch[0]=(lf<=mid-1)?build(lf,mid-1):null;42 o->ch[1]=(mid+1<=rg)?build(mid+1,rg):null;43 o->maintain();44 return o;45 }46 void splay(Node *&o,int k) {47 o->pushdown();48 int d=o->cmp(k);49 if(d==1) k-=o->ch[0]->siz+1;50 if(d!=-1) splay(o->ch[d],k), rotate(o,d^1);51 }52 Node *merge(Node *left,Node *right) {53 if(left==null) return right;54 splay(left,left->siz);55 left->ch[1]=right;left->maintain();56 return left;57 }58 void split(Node *o,int k,Node *&left,Node *&right) {59 if(k==0) left=null, right=o;60 else {61 splay(o,k);62 left=o;right=o->ch[1];63 o->ch[1]=null;left->maintain();64 }65 }66 void print(Node *o) {67 if(o==null) return ;68 o->pushdown();69 print(o->ch[0]);70 printf("%d ",o->val);71 print(o->ch[1]);72 }73 int main() {74 null->ch[0]=null->ch[1]=null;75 int n, q, lf, rg;76 scanf("%d%d",&n,&q);77 //for( int i = 1; i <= n; i++ ) scanf("%d",&aa[i]);78 root=build(1,n);79 //printf("ROOT_SEQ:");print(root);printf("\n");80 while(q--) {81 scanf("%d%d",&lf,&rg);82 Node *left, *mid, *right, *o;83 split(root,rg,mid,right);84 split(mid,lf-1,left,mid);85 //printf("LEFT_SEQ:");print(left);printf("\n");86 //printf("MID_SEQ:");print(mid);printf("\n");87 //printf("RIGHT_SEQ:");print(right);printf("\n");88 mid->rev^=1;89 root=merge(merge(left,mid),right);90 //printf("ROOT_SEQ:");print(root);printf("\n");91 }92 print(root);printf("\n");93 return 0;94 }95
1 /************************************************************** 2 Problem: 3223 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:2004 ms 7 Memory:2776 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 const int N = 100010; 13 struct Node { 14 int val, siz; 15 bool rev; 16 Node *ch[2]; 17 int cmp(int k) { 18 if(k<=ch[0]->siz) return 0; 19 if(k<=ch[0]->siz+1) return -1; 20 return 1; 21 } 22 void pushdown() {if(rev) { 23 std::swap(ch[0],ch[1]); 24 ch[0]->rev^=1; 25 ch[1]->rev^=1; 26 rev = 0; 27 }} 28 void maintain() { 29 siz=ch[0]->siz+ch[1]->siz+1; 30 } 31 }pool[N], *tail=pool, *null=pool, *root; 32 //int aa[N]; 33 void rotate(Node *&o,int d) { 34 Node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o; 35 o->maintain();k->maintain();o=k; 36 } 37 Node *build(int lf,int rg) { 38 Node *o=++tail; 39 int mid=(lf+rg)>>1; 40 o->val=mid;//aa[mid]; 41 o->ch[0]=(lf<=mid-1)?build(lf,mid-1):null; 42 o->ch[1]=(mid+1<=rg)?build(mid+1,rg):null; 43 o->maintain(); 44 return o; 45 } 46 void splay(Node *&o,int k) { 47 o->pushdown(); 48 int d=o->cmp(k); 49 if(d==1) k-=o->ch[0]->siz+1; 50 if(d!=-1) { 51 Node *p=o->ch[d]; 52 p->pushdown(); 53 int d2=p->cmp(k); 54 int k2=(d2==0?k:k-p->ch[0]->siz-1); 55 if(d2!=-1) { 56 splay(p->ch[d2],k2); 57 if(d==d2) rotate(o,d^1);else rotate(o->ch[d],d); 58 } 59 rotate(o,d^1); 60 } 61 } 62 Node *merge(Node *left,Node *right) { 63 if(left==null) return right; 64 splay(left,left->siz); 65 left->ch[1]=right;left->maintain(); 66 return left; 67 } 68 void split(Node *o,int k,Node *&left,Node *&right) { 69 if(k==0) left=null, right=o; 70 else { 71 splay(o,k); 72 left=o;right=o->ch[1]; 73 o->ch[1]=null;left->maintain(); 74 } 75 } 76 void print(Node *o) { 77 if(o==null) return ; 78 o->pushdown(); 79 print(o->ch[0]); 80 printf("%d ",o->val); 81 print(o->ch[1]); 82 } 83 int main() { 84 null->ch[0]=null->ch[1]=null; 85 int n, q, lf, rg; 86 scanf("%d%d",&n,&q); 87 //for( int i = 1; i <= n; i++ ) scanf("%d",&aa[i]); 88 root=build(1,n); 89 //printf("ROOT_SEQ:");print(root);printf("\n"); 90 while(q--) { 91 scanf("%d%d",&lf,&rg); 92 Node *left, *mid, *right, *o; 93 split(root,rg,mid,right); 94 split(mid,lf-1,left,mid); 95 //printf("LEFT_SEQ:");print(left);printf("\n"); 96 //printf("MID_SEQ:");print(mid);printf("\n"); 97 //printf("RIGHT_SEQ:");print(right);printf("\n"); 98 mid->rev^=1; 99 root=merge(merge(left,mid),right);100 //printf("ROOT_SEQ:");print(root);printf("\n");101 }102 print(root);printf("\n");103 return 0;104 }105
BZOJ 3223 Tyvj 1729 文艺平衡树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。