[题解]bzoj 3223 文艺平衡树

3223: Tyvj 1729 文艺平衡树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 3884 Solved: 2235
[Submit][Status][Discuss]

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是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 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

Source

平衡树

[Submit][Status][Discuss]

　　　　不是特别难，打个lazy标记就行了，详见[Splay]

 /**

  * bzoj

  * Problem#3223

  * Accepted

  * Time:2012ms

  * Memory:4336k

  */

 #include<iostream>

 #include<fstream>

 #include<sstream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<ctime>

 #include<cctype>

 #include<cmath>

 #include<algorithm>

 #include<stack>

 #include<queue>

 #include<set>

 #include<map>

 #include<vector>

 using namespace std;

 typedef bool boolean;

 #define smin(a, b)    (a) = min((a), (b))

 #define smax(a, b)    (a) = max((a), (b))

 template<typename T>

 inline void readInteger(T& u){

     char x;

     int aFlag = ;

     while(!isdigit((x = getchar())) && x != '-' && x != -);

     if(x == -)    return;

     if(x == '-'){

         x = getchar();

         aFlag = -;

     }

     for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');

     ungetc(x, stdin);

     u *= aFlag;

 }

 template<typename T>

 class SplayNode {

     public:

         T data;

         int s;

         boolean lazy;

         SplayNode* next[];

         SplayNode* father;

         SplayNode():s(), lazy(){

             memset(next, , sizeof(next));

         }

         SplayNode(T data, SplayNode* father):data(data), father(father), s(), lazy(){

             memset(next, , sizeof(next));

         }

         int cmp(T a){

             if(a == data)    return -;

             return (a > data) ? () : ();

         }

         int getWhich(SplayNode* p){

             return (next[] == p) ? () : ();

         }

         void maintain(){

             s = ;

             for(int i = ; i < ; i++)

                 if(next[i] != NULL)

                     s += next[i]->s;

         }

         void pushDown(){

             swap(next[], next[]);

             for(int i = ; i < ; i++)

                 if(next[i] != NULL)

                     next[i]->lazy ^= ;

             lazy = false;

         }

 };

 template<typename T>

 class Splay {

     protected:

         inline static void rotate(SplayNode<T>*& node, int d){

             SplayNode<T> *father = node->father;

             SplayNode<T> *newRoot = node->next[d ^ ];

             if(newRoot->lazy)    newRoot->pushDown();

             node->next[d ^ ] = newRoot->next[d];

             node->father = newRoot;

             newRoot->next[d] = node;

             newRoot->father = father;

             if(node->next[d ^ ] != NULL)    node->next[d ^ ]->father = node;

             if(father != NULL)    father->next[father->getWhich(node)] = newRoot;

             node->maintain();

             node->father->maintain();

         }

         static SplayNode<T>* insert(SplayNode<T>*& node, SplayNode<T>* father, T data){

             if(node == NULL){

                 node = new SplayNode<T>(data, father);

                 return node;

             }

             int d = node->cmp(data);

             if(d == -)    return NULL;

             SplayNode<T>* res = insert(node->next[d], node, data);

             if(res != NULL)    node->maintain();

             return res;

         }

         static SplayNode<T>* findKth(SplayNode<T>*& node, int k){

             if(node->lazy)    node->pushDown();

             int ls = (node->next[] != NULL) ? (node->next[]->s) : ();

             if(k >= ls +  && k <= ls + )    return node;

             if(k <= ls)    return findKth(node->next[], k);

             return findKth(node->next[], k - ls - );

         }

     public:

         SplayNode<T> *root;

         Splay(){    }

         inline void splay(SplayNode<T>* node, SplayNode<T>* father){

             if(node == father)    return;

             while(node->father != father){

                 SplayNode<T>* f = node->father;

                 int fd = f->getWhich(node);

                 SplayNode<T>* ff = f->father;

                 if(ff == father){

                     rotate(f, fd ^ );

                     break;

                 }

                 int ffd = ff->getWhich(f);;

                 if(ffd == fd){

                     rotate(ff, ffd ^ );

                     rotate(f, fd ^ );

                 }else{

                     rotate(f, fd ^ );

                     rotate(ff, ffd ^ );

                 }

             }

             if(father == NULL)

                 root = node;

         }

         inline SplayNode<T>* insert(T data){

             SplayNode<T>* res = insert(root, NULL, data);

             if(res != NULL)    splay(res, NULL);

             return res;

         }

         inline SplayNode<T>* findKth(int k, SplayNode<T>* father){

             if(k <=  || k > root->s)    return NULL;

             SplayNode<T>* p = findKth(root, k);

             splay(p, father);

             return p;

         }

         SplayNode<T>* split(int from, int end){

             if(from > end)    return NULL;

             if(from ==  && end == root->s){

                 findKth(, NULL);

                 return this->root;

             }

             if(from == ){

                 findKth(end + , NULL);

                 findKth(from, root);

                 return root->next[];

             }

             if(end == root->s){

                 findKth(from - , NULL);

                 findKth(end, root);

                 return root->next[];

             }

             findKth(end + , NULL);

             findKth(from - , root);

             return root->next[]->next[];

         }

         void out(SplayNode<T>* node){

             if(node == NULL)    return;

             if(node->lazy)    node->pushDown();

             out(node->next[]);

             printf("%d ", node->data);

             out(node->next[]);

         }

         void debugOut(SplayNode<T>* node){    //调试使用函数，打印Splay

             if(node == NULL)    return;

             cout << node->data << "(" << node->s << "," << ((node->father == NULL) ? (-) : (node->father->data)) << "," << node->lazy << "){";

             debugOut(node->next[]);

             cout <<    ",";

             debugOut(node->next[]);

             cout << "}";

         }

 };

 int n, m;

 Splay<int> s;

 int main(){

     readInteger(n);

     readInteger(m);

     for(int i = ; i <= n; i++){

         s.insert(i);

     }

     for(int i = , a, b; i<= m; i++){

         readInteger(a);

         readInteger(b);

         if(a == b)    continue;

         SplayNode<int>* p = s.split(a, b);

         p->lazy ^= ;

     }

     s.out(s.root);

     return ;

 }

巴特西