第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n)  m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n 

输出一行n个数字，表示原始序列经过m次变换后的结果 

N,M<=100000

平衡树

  1 /**  2  * bzoj  3  * Problem#3223  4  * Accepted  5  * Time:2012ms  6  * Memory:4336k  7  */  8 #include<iostream>  9 #include<fstream> 10 #include<sstream> 11 #include<cstdio> 12 #include<cstdlib> 13 #include<cstring> 14 #include<ctime> 15 #include<cctype> 16 #include<cmath> 17 #include<algorithm> 18 #include<stack> 19 #include<queue> 20 #include<set> 21 #include<map> 22 #include<vector> 23 using namespace std; 24 typedef bool boolean; 25 #define smin(a, b)    (a) = min((a), (b)) 26 #define smax(a, b)    (a) = max((a), (b)) 27 template<typename T> 28 inline void readInteger(T& u){ 29     char x; 30     int aFlag = 1; 31     while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 32     if(x == -1)    return; 33     if(x == ‘-‘){ 34         x = getchar(); 35         aFlag = -1; 36     } 37     for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 3) + (u << 1) + x - ‘0‘); 38     ungetc(x, stdin); 39     u *= aFlag; 40 } 41  42 template<typename T> 43 class SplayNode { 44     public: 45         T data; 46         int s; 47         boolean lazy; 48         SplayNode* next[2]; 49         SplayNode* father; 50         SplayNode():s(1), lazy(0){ 51             memset(next, 0, sizeof(next)); 52         } 53         SplayNode(T data, SplayNode* father):data(data), father(father), s(1), lazy(0){ 54             memset(next, 0, sizeof(next)); 55         } 56         int cmp(T a){ 57             if(a == data)    return -1; 58             return (a > data) ? (1) : (0); 59         } 60         int getWhich(SplayNode* p){ 61             return (next[0] == p) ? (0) : (1); 62         } 63         void maintain(){ 64             s = 1; 65             for(int i = 0; i < 2; i++) 66                 if(next[i] != NULL) 67                     s += next[i]->s; 68         } 69         void pushDown(){ 70             swap(next[0], next[1]); 71             for(int i = 0; i < 2; i++) 72                 if(next[i] != NULL) 73                     next[i]->lazy ^= 1; 74             lazy = false; 75         } 76 }; 77  78 template<typename T> 79 class Splay { 80     protected: 81         inline static void rotate(SplayNode<T>*& node, int d){ 82             SplayNode<T> *father = node->father; 83             SplayNode<T> *newRoot = node->next[d ^ 1]; 84             if(newRoot->lazy)    newRoot->pushDown(); 85             node->next[d ^ 1] = newRoot->next[d]; 86             node->father = newRoot; 87             newRoot->next[d] = node; 88             newRoot->father = father; 89             if(node->next[d ^ 1] != NULL)    node->next[d ^ 1]->father = node; 90             if(father != NULL)    father->next[father->getWhich(node)] = newRoot; 91             node->maintain(); 92             node->father->maintain(); 93         } 94          95         static SplayNode<T>* insert(SplayNode<T>*& node, SplayNode<T>* father, T data){ 96             if(node == NULL){ 97                 node = new SplayNode<T>(data, father); 98                 return node; 99             }100             int d = node->cmp(data);101             if(d == -1)    return NULL;102             SplayNode<T>* res = insert(node->next[d], node, data);103             if(res != NULL)    node->maintain();104             return res;105         }106         107         static SplayNode<T>* findKth(SplayNode<T>*& node, int k){108             if(node->lazy)    node->pushDown();109             int ls = (node->next[0] != NULL) ? (node->next[0]->s) : (0);110             if(k >= ls + 1 && k <= ls + 1)    return node;111             if(k <= ls)    return findKth(node->next[0], k);112             return findKth(node->next[1], k - ls - 1);113         }114         115     public:116         SplayNode<T> *root;117         118         Splay(){    }119 120         inline void splay(SplayNode<T>* node, SplayNode<T>* father){121             if(node == father)    return;122             while(node->father != father){123                 SplayNode<T>* f = node->father;124                 int fd = f->getWhich(node);125                 SplayNode<T>* ff = f->father;126                 if(ff == father){127                     rotate(f, fd ^ 1);128                     break;129                 }130                 int ffd = ff->getWhich(f);;131                 if(ffd == fd){132                     rotate(ff, ffd ^ 1);133                     rotate(f, fd ^ 1);134                 }else{135                     rotate(f, fd ^ 1);136                     rotate(ff, ffd ^ 1);137                 }138             }139             if(father == NULL)140                 root = node;141         }142         143         inline SplayNode<T>* insert(T data){144             SplayNode<T>* res = insert(root, NULL, data);145             if(res != NULL)    splay(res, NULL);146             return res;147         }148         149         inline SplayNode<T>* findKth(int k, SplayNode<T>* father){150             if(k <= 0 || k > root->s)    return NULL;151             SplayNode<T>* p = findKth(root, k);152             splay(p, father);153             return p;154         }155         156         SplayNode<T>* split(int from, int end){157             if(from > end)    return NULL;158             if(from == 1 && end == root->s){159                 findKth(1, NULL);160                 return this->root;161             }162             if(from == 1){163                 findKth(end + 1, NULL);164                 findKth(from, root);165                 return root->next[0];166             }167             if(end == root->s){168                 findKth(from - 1, NULL);169                 findKth(end, root);170                 return root->next[1];171             }172             findKth(end + 1, NULL);173             findKth(from - 1, root);174             return root->next[0]->next[1];175         }176         177         void out(SplayNode<T>* node){178             if(node == NULL)    return;179             if(node->lazy)    node->pushDown();180             out(node->next[0]);181             printf("%d ", node->data);182             out(node->next[1]);183         }184         185         void debugOut(SplayNode<T>* node){    //调试使用函数，打印Splay 186             if(node == NULL)    return;187             cout << node->data << "(" << node->s << "," << ((node->father == NULL) ? (-9999) : (node->father->data)) << "," << node->lazy << "){";188             debugOut(node->next[0]);189             cout <<    ",";190             debugOut(node->next[1]);191             cout << "}";192         }193 };194 195 int n, m;196 Splay<int> s;197 198 int main(){199     readInteger(n);200     readInteger(m);201     for(int i = 1; i <= n; i++){202         s.insert(i);203     }204     for(int i = 1, a, b; i<= m; i++){205         readInteger(a);206         readInteger(b);207         if(a == b)    continue;208         SplayNode<int>* p = s.split(a, b);209         p->lazy ^= 1;210     }211     s.out(s.root);212     return 0;213 }