题目不说了，就是区间翻转
传送门：BZOJ 3223 和 CodeVS 3243
第一道题中是1~n的区间翻转，而第二道题对于每个1~n还有一个附加值
实际上两道题的思路是一样的，第二题把值对应到位置就行了
这里我们用伸展树来解决，但其中用到了线段树中的标记思想
对于一个长度的为n的序列，我们把它的每一位向后移动一位，即1~n → 2~n+1，然后再在序列前后分别补上一位：1和n+2。所以我们需要建立一颗节点数为n+2的伸展树，而原序列中的1~n位分别对应新序列中的2~n+1位。
对于每次询问的l和r，实际上就是l+1和r+1，首先找到l+1前一位对应的元素和r+1后一位对应的元素，即l和r+2分别对应的元素的序号。然后将l对应元素通过splay操作旋转到根节点，将r+2对应元素旋转到根节点的右儿子，由排序二叉树的性质可知，r+2的左儿子就是序列l+1~r+1，也就是询问中需要翻转的区间。对r+2的左儿子直接打上标记，在之后找元素序号的时候要记得把标记下传，同时用swap操作来达到翻转的目的。
splay操作和rotate操作在此不赘述。
最后输出的时候，同样查找2~n+1对应的元素序号，将得到的值减1还原，对于CodeVS 3243就再套一个值输出即可。
这里给出BZOJ 3223的代码。
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <ctime>
#include <queue>
#include <string>
#include <map>
typedef long long ll;
using namespace std;
const int MAXN = ;
int n, m;
int root;
int son[MAXN][], fa[MAXN], lazy[MAXN], siz[MAXN]; inline int gi() {
char c;
int sum = , f = ;
c = getchar();
while (c < '' || c > '') {
if (c == '-')
f = -;
c = getchar();
}
while (c >= '' && c <= '') {
sum = sum * + c - '';
c = getchar();
}
return sum * f;
} void build(int l, int r, int f) {
if (l > r)
return;
if (l == r) {
siz[l] = ;
fa[l] = f;
son[f][l > f] = l;
return;
}
int mid = (l + r) >> ;
build(l, mid - , mid);
build(mid + , r, mid);
siz[mid] = siz[son[mid][]] + siz[son[mid][]] + ;
fa[mid] = f;
son[f][mid > f] = mid;
} void pushdown(int o) {
swap(son[o][], son[o][]);
lazy[son[o][]] ^= ;
lazy[son[o][]] ^= ;
lazy[o] = ;
} int find(int o, int p) {
if (lazy[o])
pushdown(o);
int l = son[o][];
int r = son[o][];
if (siz[l] + == p)
return o;
if (siz[l] >= p)
return find(l, p);
else
return find(r, p - siz[l] - );
} void rotate(int x, int &to) {
int l, r;
int f = fa[x];
int ff = fa[f];
l = son[f][] == x ? : ;
r = l ^ ;
if (f == to)
to = x;
else
son[ff][son[ff][] == f] = x;
fa[x] = fa[f];
fa[f] = x;
fa[son[x][r]] = f;
son[f][l] = son[x][r];
son[x][r] = f;
siz[f] = siz[son[f][]] + siz[son[f][]] + ;
siz[x] = siz[son[x][]] + siz[son[x][]] + ;
} void splay(int x, int &to) {
while (x != to) {
int f = fa[x];
int ff = fa[f];
if (f != to) {
if ((son[f][] == x) ^ (son[ff][] == f))
rotate(x, to);
else
rotate(f, to);
}
rotate(x, to);
}
} void reserve(int l, int r) {
int x = find(root, l);
int y = find(root, r + );
splay(x, root);
splay(y, son[x][]);
lazy[son[y][]] ^= ;
} int main() {
n = gi();
m = gi();
build(, n + , );
root = (n + ) >> ;
for (int i = ; i <= m; i++) {
int l = gi();
int r = gi();
reserve(l, r);
}
for (int i = ; i <= n + ; i++)
printf("%d ", find(root, i) - );
return ;
}