POJ 3580 较复杂的Splay区间维护题解题报告

浅谈Splay：

在做完这道题后，我对Splay又有了一些新的理解，先简单的介绍一下： 1. 在完成最普通的插入和查询时，Splay的时间复杂度可能会高于Treap等平衡树，但是只用它来维护点的信息是大材小用了的。 2. Splay的核心操作就是伸展（将某个点旋转到某个点的下方），它不仅维护了一颗平衡树，还支持许多十分“高级”的功能（例如区间维护和动态树上的Preferred Path维护等），他们都是基于最基本的伸展操作的。 3. Splay的可拓展性非常好，在原先的基础上只需添加一些附加的值即可完成那些看起来比较复杂的操作，同时可以利用类似线段树的Lazy思想优化时间复杂度。 4. Splay的常数是非常大的，在多数情况下log(n)只是理想状态下的情况，所以对于程序竞赛，要慎重考虑。

好的，接下来切入正题~~~

题目大意：

要求维护一个序列，支持如下几种操作: 1. 一段区间全部增加一个值 2. 翻转某一段区间 3. 将某一段区间滚动一定距离后插回原来的位置 4. 在第x个数后插入一个值T 5. 删除某一个点 6. 询问某段区间的最小值

分析：

我们可以大致把操作进行一个分类:

1. 插入、删除:

对于插入操作，我们可以将x转到根部，再将x+1转到x下方然后在x+1的左子树中插入新节点即可。 那么类似的对于删除，我们也可以先将x-1转到根部，x+1转到根下方，那么x就是x+1的左子树，直接删除即可~

2. 询问：

对于询问区间(x,y)的最值，只需将x-1转到根，然后将y+1转到x-1的下方，于是我们需要维护的区间就在y+1的左子树的所有点的集合里了，直接输出节点信息即可。

3. 翻转、区间增加：

和询问类似，先将x-1转到根，然后将y+1转到x-1的下方，然后对y+1的左子树打标记即可~，注意及时更新标记。

4. 滚动：

可以发现，滚动某个区间就等价于交换区间的两部分，我们设这个中点为z，那么我们的目的就是交换（x, z) 和 (z+1, y), 我们可以先将z转到根，然后将y+1转到z的下方，于是y+1的左子树就对应了区间（z+1，y）然后我们将这一段切下来，继续将x-1转到根，再将x转到x-1下方，最后将区间(z+1, y)接到x-1的左边即可。

代码：

#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 200000 + 10; struct SplayTree { int n, root; int Val[maxn]; int Add[maxn], Min[maxn], Rev[maxn]; int fa[maxn], c[maxn][2], size[maxn]; void init() { n = root = 0; memset(c, 0, sizeof(c)); memset(fa, 0, sizeof(fa)); } void Push_up(int u) { Min[u] = Val[u]; size[u] = size[c[u][0]] + size[c[u][1]] + 1; if(c[u][0]) Min[u] = min(Min[u], Min[c[u][0]]); if(c[u][1]) Min[u] = min(Min[u], Min[c[u][1]]); } void Push(int u) { if(fa[u]) Push(fa[u]); Push_down(u); } void Push_down(int u) { if(Add[u]) { if(c[u][0]) Add[c[u][0]] += Add[u], Val[c[u][0]] += Add[u], Min[c[u][0]] += Add[u]; if(c[u][1]) Add[c[u][1]] += Add[u], Val[c[u][1]] += Add[u], Min[c[u][1]] += Add[u]; }if(Rev[u]) { if(c[u][0]) Rev[c[u][0]] ^= 1; if(c[u][1]) Rev[c[u][1]] ^= 1; swap(c[u][0], c[u][1]); }Add[u] = Rev[u] = 0; } int Newnode(int key) { size[++n] = 1; Add[n] = Rev[n] = 0; Val[n] = Min[n] = key; return n; } void rotate(int u) { int v = fa[u], w = fa[v], t = c[v][1] == u; fa[c[u][t^1]] = v, c[v][t] = c[u][t^1]; c[u][t^1] = v, fa[u] = w, fa[v] = u; if(root == v) root = u; else c[w][c[w][1] == v] = u; Push_up(v); } void Splay(int u, int p) { Push(u); while(fa[u] != p) { int v = fa[u], w = fa[v]; if(fa[v] == p) rotate(u); else if((c[v][0] == u) == (c[w][0] == v)) rotate(v), rotate(u); else rotate(u), rotate(u); }Push_up(u); } void insert(int key) { Newnode(key); c[root][1] = n; fa[n] = root; Splay(n, 0); } int find(int u, int k) { Push_down(u); int t = size[c[u][0]] + 1; if(t == k) return u; else { if(t > k) return find(c[u][0], k); else return find(c[u][1], k-t); } } void update(int u, int v, int w) { int x = find(root, u), y = find(root, v+2); Splay(x, 0), Splay(y, root); Add[c[y][0]] += w; Val[c[y][0]] += w; Min[c[y][0]] += w; } void Reverse(int u, int v) { int x = find(root, u), y = find(root, v+2); Splay(x, 0), Splay(y, root); Rev[c[y][0]] ^= 1; } void Revolve(int u, int v, int w) { int m = v - u + 1; w %= m; w = (w + m) % m; int x = find(root, u), y = find(root, u+1); int _x = find(root, v-w+1), _y = find(root, v+2); Splay(_x, 0), Splay(_y, root); int p = c[_y][0]; c[_y][0] = 0; Splay(x, 0), Splay(y, root); c[y][0] = p; fa[p] = y; } void Join(int u, int v) { int x = find(root, u+1), y = find(root, u+2); Splay(x, 0), Splay(y, root); c[y][0] = Newnode(v); fa[n] = y; } void del(int u) { int x = find(root, u), y = find(root, u+2); Splay(x, 0), Splay(y, root); c[y][0] = 0; } int query(int u, int v) { int x = find(root, u), y = find(root, v+2); Splay(x, 0), Splay(y, root); return Min[c[y][0]]; } }Spt; char s[20]; int n, q, u, v, w; int main() { #ifndef ONLINE_JUDGE freopen("data.txt", "r", stdin); freopen("ans.txt", "w", stdout); #endif while(scanf("%d", &n) == 1 && n) { Spt.init(); Spt.root = Spt.Newnode(INF); for(int i=1; i<=n; i++) { scanf("%d", &u); Spt.insert(u); }Spt.insert(INF); scanf("%d", &q); while(q--) { scanf("%s", s); if(s[0] == 'A') { scanf("%d%d%d", &u, &v, &w); if(u > v) swap(u, v); Spt.update(u, v, w); }else if(s[0] == 'R' && s[3] == 'E') { scanf("%d%d", &u, &v); if(u > v) swap(u, v); Spt.Reverse(u, v); }else if(s[0] == 'R' && s[3] == 'O') { scanf("%d%d%d", &u, &v, &w); if(u > v) swap(u, v); Spt.Revolve(u, v, w); }else if(s[0] == 'I') { scanf("%d%d", &u, &v); Spt.Join(u, v); }else if(s[0] == 'D') { scanf("%d", &u); Spt.del(u); }else if(s[0] == 'M') { scanf("%d%d", &u, &v); if(u > v) swap(u, v); printf("%d\n", Spt.query(u, v)); } } } return 0; }