传送门：>Here<
解法分析
用splay来维护这个序列。
一直没有搞明白的是，这里的splay的节点究竟维护的是什么？是权值吗？肯定不是，因为区间是会翻转的，如果维护权值的话很快平衡树就不再满足性质。
然而从头到尾，唯一始终统一的就是位置——始终是1~n. 因此考虑用节点来维护位置。
这样在维护splay的时候，翻转一段区间就相当于修改了这一段区间的位置，使原来小的现在大了，原来大的现在小了。放在树上形象的看，就是原来作为父节点的左儿子的统统称为了右儿子。反之亦然。因此只要找出连续的那一段区间，并且翻转左右子树即可。注意为了减少操作次数，可以打懒标记。
如何找出连续的那一段目标区间？由于要翻转的是区间$[l, r]$，我们可以找到位置（注意，这里的位置也就是平衡树维护的权值的排名了，因此位置i也就是排名第i的）l-1和r+1的点，分别旋转到根节点和根节点的右子树上。这样，根节点的右子节点的左子树就是这段区间了。（想一想，为什么）。特殊的，当边界到达1或n时会溢出，因此我们加入哨兵节点-1和n+1。这样位置i就是排名i+1了。
值得注意的是何时下传懒标记——根据懒标记的优良传统，不用就不翻转。那唯一要用的时候就是询问位置的时候了，因此只要find的时候下传就可以了。另外翻转两次相当于不翻转，所以用xor1会很方便。
/*By QiXingzhi*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define r read() #define Max(a,b) (((a)>(b)) ? (a) : (b)) #define Min(a,b) (((a)<(b)) ? (a) : (b)) using namespace std; typedef long long ll; const int MAXN = 100010; const int INF = 1061109567; inline int read(){ int x = 0; int w = 1; register int c = getchar(); while(c ^ '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c >= '0' && c <= '9') x = (x << 3) +(x << 1) + c - '0', c = getchar(); return x * w; } int n,m,L,R; struct Splay{ int ch[MAXN][2],size[MAXN],val[MAXN],fa[MAXN],tag[MAXN],num_node,root; inline bool Son(int f, int x){ return ch[f][1]==x; } inline void Update(int x){ size[x] = size[ch[x][1]] + size[ch[x][0]] + 1; } inline void Rotate(int x){ int f = fa[x], gf = fa[f]; bool p = Son(f, x), q = !p; ch[f][p] = ch[x][q]; fa[ch[x][q]] = f; ch[x][q] = f; fa[f] = x; fa[x] = gf; if(gf != 0){ ch[gf][Son(gf,f)] = x; }else{ root = x; } Update(x), Update(f); } inline void splay(int x, int target){ while(fa[x] != target){ int f = fa[x], gf = fa[f]; if(gf == target){ Rotate(x); return; } if(Son(gf,f) == Son(f,x)){ Rotate(f), Rotate(x); } else{ Rotate(x), Rotate(x); } } } inline void Insert(int v){ if(root == 0){ ++num_node; root = num_node; size[num_node] = 1; val[num_node] = v; return; } for(int x = root; x != 0; x = ch[x][v >= val[x]]){ bool b = v >= val[x]; if(ch[x][b] == 0){ ++num_node; ch[x][b] = num_node; size[num_node] = 1; val[num_node] = v; fa[ch[x][b]] = x; splay(ch[x][b], 0); } } } inline void Pushdown(int x){ if(x == 0) return; if(!tag[x]) return; int tmp = ch[x][0]; ch[x][0] = ch[x][1]; ch[x][1] = tmp; tag[x] = 0; tag[ch[x][0]] ^= 1; tag[ch[x][1]] ^= 1; } inline int Find(int _k){ int x = root; for(; x != 0;){ Pushdown(x); if(size[ch[x][0]] + 1 == _k){ return x; } if(size[ch[x][0]] >= _k){ x = ch[x][0]; } else{ _k -= size[ch[x][0]] + 1; x = ch[x][1]; } } } inline void Reverse(int L, int R){ if(L >= R) return; splay(Find(L), 0); splay(Find(R), root); tag[ch[ch[root][1]][0]] ^= 1; } inline void DEBUG(){ for(int i = 1; i <= n; ++i){ printf("%d-->%d lson:%d rson:%d ",i,val[i],ch[i][0],ch[i][1]); } } }qxz; int main(){ // freopen(".in","r",stdin); n=r, m=r; qxz.Insert(-1); qxz.Insert(n+1); for(int i = 1; i <= n; ++i){ qxz.Insert(i); } // qxz.DEBUG(); for(int i = 1; i <= m; ++i){ L=r, R=r; qxz.Reverse(L,R+2); } for(int i = 1; i <= n; ++i){ printf("%d ", qxz.val[qxz.Find(i+1)]); } return 0; }