ZOJ Monthly, March 2014,3765 Lights 基本上是Splay 的基本操作，并维护区间上的信息
留作模板，写下对Splay树的理解和注意的问题。
（1）版本选择：关于Splay的模板有网上流传的版本和刘汝佳白书的版本，个人感觉白书上的更好些，但基于网上参考比较多选择了网上版本
（2）关于Splay树通常有维护区间（维护序列）和平衡树两方面的应用
（3）！注意：up和down的使用地方
（4）！up和down函数实现是注意具体细节
（5）！！重要理解：Init（）函数中Build（）之前先生成了2各节点，分别是序列的最左端和序列的最右端（或平衡树中最小值和最大值），以避免出错。
因为多了两个节点，在使用时就要注意1)不能对维护的区间信息产生干扰
2)区间操作，Splay和RTO是就要注意参数的取值
（6）理解：个人感觉，使用Splay是将维护区间的信息部分和区间操作部分分开理解不易混乱
仍待理解。。持续更新。。。
本题的代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;
#define ll ch[x][0]
#define rr ch[x][1]
#define KT (ch[ch[rt][1]][0])
const int maxn = 300100;
int a[maxn], flage[maxn];
int n, m;
struct SplayTree{
///基本数据定义
int ch[maxn][2];
int sz[maxn], pre[maxn];
int rt, tot;
///题意数据定义
int val[maxn], flg[maxn], GCD[maxn][2];
///Splay树的基本旋转操作函数
void Rotate(int x, int f)
{
int y = pre[x];
// down(y); down(x);///
ch[y][!f] = ch[x][f];
pre[ch[x][f]] = y;
pre[x] = pre[y];
if (pre[x]) ch[pre[y]][ch[pre[y]][1] == y] = x;
ch[x][f] = y;
pre[y] = x;
up(y);///
}
void Splay(int x, int goal)
{
// down(x);///
while (pre[x] != goal)
{
if (pre[pre[x]] == goal) Rotate(x, ch[pre[x]][0] == x);
else
{
int y = pre[x], z = pre[y];
int f = ( ch[z][0] == y );
if (ch[y][f] == x) Rotate(x, !f), Rotate(x, f);
else Rotate(y, f), Rotate(x, f);
}
}
up(x);///
if (goal == 0) rt = x;
}
void RTO(int k, int goal)
{
int x = rt;
while (sz[ll] + 1 != k)
{
if (k < sz[ll] + 1) x = ll;
else
{
k -= (sz[ll] + 1);
x = rr;
}
}
Splay(x, goal);
}
///Splay树的生成函数
void newnode(int &x, int c, int state, int f)///
{
x = ++tot;
ll = rr = 0;
sz[x] = 1; pre[x] = f;
val[x] = c; flg[x] = state;
GCD[x][state] = c;
GCD[x][!state] = -1;
}
void build(int &x, int l, int r, int f)///
{
if (l > r) return ;
int m = (l + r) >> 1;
newnode(x, a[m], flage[m], f);
build(ll, l, m - 1, x);
build(rr, m + 1, r, x);
up(x);
}
void Init(int n)
{
ch[0][0] = ch[0][1] = pre[0] = sz[0] = 0;
GCD[0][0] = GCD[0][1] = -1;
flg[0] = val[0] = 0;///????
rt = tot = 0;
newnode(rt, -1, 0, 0);
newnode(ch[rt][1], -1, 0, rt);
build(KT, 1, n, ch[rt][1]);///
up(ch[rt][1]); up(rt);///
}
///区间操作相关up(), down()
void up(int x)///!!!
{
sz[x] = sz[ll] + sz[rr] + 1;///!!!
GCD[x][flg[x]] = val[x];///!!!!
GCD[x][!flg[x]] = -1;
for (int i = 0; i < 2; i++)
{
if (GCD[ll][i] != -1)
{
if (GCD[x][i] != -1) GCD[x][i] = __gcd(GCD[x][i], GCD[ll][i]);
else GCD[x][i] = GCD[ll][i];
}
if (GCD[rr][i] != -1)
{
if (GCD[x][i] != -1) GCD[x][i] = __gcd(GCD[x][i], GCD[rr][i]);
else GCD[x][i] = GCD[rr][i];
}
}
}
///区间查询
void solve_Q(int L, int R, int state)
{
RTO(L, 0);
RTO(R + 2, rt);
printf("%d\n", GCD[KT][state]);
}
///插入一个节点
void solve_I(int L, int value, int state)
{
RTO(L + 1, 0);
RTO(L + 2, rt);
int x;
newnode(x, value, state, ch[rt][1]);///!!!
KT = x;
up(ch[rt][1]); up(rt);
}
///删除一个节点
void solve_D(int L)
{
RTO(L, 0);
RTO(L + 2, rt);
KT = 0;
up(ch[rt][1]); up(rt);
}
///更改节点信息
void solve_R(int L)
{
RTO(L + 1, 0); flg[rt] ^= 1;
up(rt);
}
void solve_M(int L, int value)
{
RTO(L + 1, 0); val[rt] = value;
up(rt);
}
///题意相关函数
void solve(int m)
{
char op;
int L, R, state, value;
while (m--)
{
scanf(" %c", &op);
if (op == ‘Q‘)
{
scanf("%d%d%d", &L, &R, &state);
solve_Q(L, R, state);
}
else if (op == ‘I‘)
{
scanf("%d%d%d", &L, &value, &state);
solve_I(L, value, state);
}
else if (op == ‘D‘)
{
scanf("%d", &L);
solve_D(L);
}
else if (op == ‘R‘)
{
scanf("%d", &L);
solve_R(L);
}
else if (op == ‘M‘)
{
scanf("%d%d", &L, &value);
solve_M(L, value);
}
}
}
}sp;
int main()
{
while (cin >> n >> m)
{
for (int i = 1; i <= n; i++)
scanf("%d%d", &a[i], &flage[i]);
sp.Init(n);
sp.solve(m);
}
}
ZOJ Monthly, March 2014,3765 Lights (Splay 基本操作，并维护区间上的信息 * 模板),布布扣,bubuko.com
ZOJ Monthly, March 2014,3765 Lights (Splay 基本操作，并维护区间上的信息 * 模板)
原文：http://blog.csdn.net/guognib/article/details/20395203