这道题所需要的区间反转操作是Splay的主要功能之一——维护区间信息的一个应用。如何维护呢？我们考虑区间([l, r])，我们如何在Splay中将它变成一个可操作的东西呢？考虑把整个区间搞到一棵子树上去，然后用类似于线段树打懒标记的方法维护信息。
具体来说，我们把区间节点(l-1)旋到整棵树的根节点的位置，然后用把节点(r+1)旋到根节点的右儿子的位置。这样搞完之后，根节点的右子树的左子树就是区间([l,r])了，我们直接在这棵子树的根节点上打上一个flip标记（准确地说是更新它的flip标记，因为在同一节点上flip两次等于什么都没做）即可。之后，如果我们需要深入访问它的子树，我们就需要将这个懒标记下传，同时交换它的两棵子树的位置。当然，在实际实现中，我们其实是把(l)旋到根节点的位置，最后把所有答案减1，避免边界bug的产生。具体细节参考代码。
// BZOJ 3223, Splay
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define read(x) scanf("%d", &x)
#define rep(i,a,b) for (int i=a; i<=b; i++)
#define dep(i,a,b) for (int i=a; i>=b; i--)
#define fill(a,x) memset(a, x, sizeof(a))
int n, m, l, r;
struct Node {
Node *son[2];
int v, s, flip;
int cmp(int x) const {
int d = x - son[0]->s;
if (d == 1) return -1; // 找到了这个节点
return d <= 0 ? 0 : 1; // 查询的节点在左子树/右子树
}
void maintain() { s = son[1]->s + son[0]->s +1; }
void pushdown() {
if (flip) {
flip = false;
swap(son[0], son[1]);
son[0]->flip = !son[0]->flip;
son[1]->flip = !son[1]->flip;
}
}
} *root;
Node *null = new Node();
void rotate(Node *&o, int d) {
Node *k = o->son[d^1];
o->son[d^1] = k->son[d];
k->son[d] = o;
o->maintain();
k->maintain();
o = k;
}
// 把序列左数第x个节点旋转到o。Ru JiaLiu的优越代码，查找伸展二合一
void splay(Node *&o, int x) {
o->pushdown();
int d = o->cmp(x);
if (d == 1) x -= (o->son[0]->s + 1);
if (d != -1) {
Node *u = o->son[d]; // 双旋，往下再找
u->pushdown(); // 把需要利用的节点的标记下传
int d2 = u->cmp(x); // 再判断要找节点和u之间的关系
int x2 = (d2 == 0 ? x : x - u->son[0]->s - 1);
if (d2 != -1) {
splay(u->son[d2], x2);
// 顺着查找，逆着旋转
if (d == d2) rotate(o, d^1); else rotate(o->son[d], d);
}
rotate(o, d^1);
}
}
int num=0;
void build(Node *&o, int sz) {
if (sz == 0) { o = null; return; }
o = new Node();
if (sz == 1) {
o->v = ++num; o->s = 1; o->flip = false;
o->son[1] = o->son[0] = null;
return;
}
o->flip = false;
build(o->son[0], sz/2);
o->v = ++num;
build(o->son[1], sz-sz/2-1);
o->maintain();
}
void init(int sz) {
null->s = 0;
build(root, sz+2);
}
void reverse(int l, int r) {
splay(root, l); // 把l旋到root，现在root的左子树的大小就是l-1
splay(root->son[1], (r+2)-l); // 把r旋到root的右儿子，它在这棵右子树的位置自然变成r-l
root->son[1]->son[0]->flip ^= 1;
}
int cnt=0, ans[N];
void print(Node *o) {
if (o!=null) {
o->pushdown();
print(o->son[0]);
ans[++cnt] = o->v;
print(o->son[1]);
}
}
void debug(Node* o) {
if(o != null) {
o->pushdown();
debug(o->son[0]);
printf("%d ", o->v-1);
debug(o->son[1]);
}
}
int main()
{
read(n); read(m);
init(n);
while (m--) {
read(l); read(r);
reverse(l, r);
}
print(root);
rep(i,2,n+1) printf("%d ", ans[i]-1);
return 0;
}
也是第一次写Splay，调了很久，还需要多写几题练练手。
还有一个大码农题… BZOJ 1895（POJ 3580）是把各种东西都要求维护了… 因为都是一个懒标记下传的方法，而且更好的Splay练习题还有很多，所以这题实在懒得写了（砸…
（之前一直不明白Splay为什么能维护序列信息，后来在黄学长博客上看了某条评论才知道，——“搜索树和序列不能同时维护”，这才把我忐忑的心安顿下来…）