Splay

Permutation Transformer

UVA - 11922
题意：1到n的排列，翻转a到b这一段并加到末尾，m次。输出最后的排列。
比着模板打的。。。orz，等有感觉了再回来写。
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 struct Node{
  5     Node* ch[2];
  6     int s;
  7     int flip;
  8     int v;
  9     int cmp(int k)const{
 10         int d=k-ch[0]->s;
 11         if(d==1) return -1;
 12         return d<=0?0:1;
 13     }
 14     void maintain(){
 15         s=ch[0]->s+ch[1]->s+1;
 16     }
 17     void pushdown(){
 18         if(flip){
 19             flip=0;swap(ch[0],ch[1]);
 20             ch[0]->flip=!ch[0]->flip;
 21             ch[1]->flip=!ch[1]->flip;
 22         }
 23     }
 24 };
 25 Node *null=new Node();
 26 
 27 void rotate(Node* &o,int d){
 28     Node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
 29     o->maintain();k->maintain();o=k;
 30 }
 31 
 32 void splay(Node* &o,int k){  //找到序列的左数第k个元素并伸展到根
 33     o->pushdown();
 34     int d=o->cmp(k);
 35     if(d==1) k-=o->ch[0]->s+1;
 36     if(d!=-1){
 37         Node* p=o->ch[d];
 38         p->pushdown();
 39         int d2=p->cmp(k);
 40         int k2=(d2==0?k:k-p->ch[0]->s-1);
 41         if(d2!=-1){
 42             splay(p->ch[d2],k2);
 43             if(d==d2) rotate(o,d^1);else rotate(o->ch[d],d);
 44         }
 45         rotate(o,d^1);
 46     }
 47 }
 48 //合并left和right，假定left的所有元素比right小。注意right可以使null，left不可以
 49 Node* merge(Node* left,Node* right){
 50     splay(left,left->s);
 51     left->ch[1]=right;
 52     left->maintain();
 53     return left;
 54 }
 55 //把o的前k小的节点放在left里，其他的放在right里，当k=o->s时，right等于null
 56 void split(Node* o,int k,Node* &left,Node* &right){
 57     splay(o,k);
 58     left=o;
 59     right=o->ch[1];
 60     o->ch[1]=null;
 61     left->maintain();
 62 }
 63 
 64 const int maxn=100000 + 10;
 65 struct SplaySequence{
 66     int n;
 67     Node seq[maxn];
 68     Node *root;
 69 
 70     Node* build(int sz){
 71         if(!sz) return null;
 72         Node* L=build(sz/2);
 73         Node* o=&seq[++n];
 74         o->v=n;
 75         o->ch[0]=L;
 76         o->ch[1]=build(sz-sz/2-1);
 77         o->flip=o->s=0;
 78         o->maintain();
 79         return o;
 80     }
 81 
 82     void init(int sz){
 83         n=0;
 84         null->s=0;
 85         root=build(sz);
 86     }
 87 };
 88 
 89 vector<int> ans;
 90 void print(Node* o){
 91     if(o!=null){
 92         o->pushdown();
 93         print(o->ch[0]);
 94         ans.push_back(o->v);
 95         print(o->ch[1]);
 96     }
 97 }
 98 
 99 SplaySequence ss;
100 int main()
101 {
102     int n,m;
103     scanf("%d%d",&n,&m);
104     ss.init(n+1);   //前面虚拟一个节点
105     while(m--){
106         int a,b;
107         scanf("%d%d",&a,&b);
108         Node *left,*mid,*right,*o;
109         split(ss.root,a,left,o);  // 如果没有虚拟结点，a将改成a-1，违反split的限制!!!
110         split(o,b-a+1,mid,right);
111         mid->flip^=1;
112         ss.root=merge(merge(left,right),mid);
113     }
114     print(ss.root);
115     for(int i=1;i<ans.size();i++)
116         printf("%d
",ans[i]-1);
117     return 0;
118 }
View Code
Looploop

HDU - 4453