题目大意
网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样 我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目 就叫序列终结者吧。【问题描述】 给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作： 1. 将 [L, R] 这个区间内的所有数加上 V。 2. 将 [L,R] 这个区间翻转，比如 1 2 3 4 变成 4 3 2 1。3. 求 [L,R] 这个区间中的最大值。最开始所有元素都是 0。
第一行两个整数 N，M。M 为操作个数。以下 M 行，每行最多四个整数，依次为 K， L， R， V。K 表示是第几种操作，如果不是第 1 种操作则 K 后面只有两个数。对于每个第3种操作，给出正确的回答。
【数据范围】N<=50000，M<=100000。
做法分析
这题还真不能用 线段树 做，Splay 是一个不错的选择
对于操作 1 将所有 [L, R] 中的数加上一个常量，可以对 Splay 树中的节点增加一个 add 域，表示以该节点为根中序遍历所得的数列中每个数要增加 add，每次执行的时候，先将 L-1 旋转到根，再把 R+1 旋转成根的儿子节点，那么，[L, R] 区间的数列就在 R+1 的左子树中了，对 R+1 的左儿子执行更新操作即可，类似于线段树的懒操作
对于操作 2 将所有 [L, R] 中的数翻转，可以对 Splay 树中的节点增加一个 rev 域，表示以该节点为根中序遍历所得的数列是否需要翻转，更新的时候还是和操作 1 一样，将 L-1 旋转到根，R+1 旋转成为 L-1 的孩子，直接对 R+1 的左儿子更新
对于操作 3，增加一个 Max 域，表示以该节点为根中序遍历得到的数列中最大值是多少，询问时，将 L-1 旋转到根，R+1 旋转成 L-1 的孩子，询问 R-1 的左儿子的 Max 即可
这里说一点细节：由于是维护数列，且涉及到区间翻转操作，所以还要增加一个 Size 域，表示以它为根的中序遍历得到的数列的个数是多少，用它来实现数列中的定位
由于涉及到翻转和统一加权操作，pushDown 和 pushUp 操作一定要想好在哪些地方需要执行
参考代码
#include <iostream>
#include <cstring>
#include <cstdio> using namespace std; const int N=, INF=0x7fffffff; struct Splay_Tree {
struct Node {
int val, Max, add, Size, son[];
bool rev;
void init(int _val) {
val=Max=_val, Size=;
add=rev=son[]=son[]=;
}
} T[N];
int fa[N], root; void pushUp(int x) {
T[x].Max=T[x].val, T[x].Size=;
if(T[x].son[]) {
T[x].Max=max(T[x].Max, T[T[x].son[]].Max);
T[x].Size+=T[T[x].son[]].Size;
}
if(T[x].son[]) {
T[x].Max=max(T[x].Max, T[T[x].son[]].Max);
T[x].Size+=T[T[x].son[]].Size;
}
} void pushDown(int x) {
if(x==) return;
if(T[x].add) {
if(T[x].son[]) {
T[T[x].son[]].val+=T[x].add;
T[T[x].son[]].Max+=T[x].add;
T[T[x].son[]].add+=T[x].add;
}
if(T[x].son[]) {
T[T[x].son[]].val+=T[x].add;
T[T[x].son[]].Max+=T[x].add;
T[T[x].son[]].add+=T[x].add;
}
T[x].add=;
}
if(T[x].rev) {
if(T[x].son[]) T[T[x].son[]].rev^=;
if(T[x].son[]) T[T[x].son[]].rev^=;
swap(T[x].son[], T[x].son[]);
T[x].rev=;
}
} void Rotate(int x, int kind) {
int y=fa[x], z=fa[y];
T[y].son[!kind]=T[x].son[kind], fa[T[x].son[kind]]=y;
T[x].son[kind]=y, fa[y]=x;
T[z].son[T[z].son[]==y]=x, fa[x]=z;
pushUp(y);
} void Splay(int x, int goal) {
if(x==goal) return;
while(fa[x]!=goal) {
int y=fa[x], z=fa[y];
pushDown(z), pushDown(y), pushDown(x);
int rx=T[y].son[]==x, ry=T[z].son[]==y;
if(z==goal) Rotate(x, rx);
else {
if(rx==ry) Rotate(y, ry);
else Rotate(x, rx);
Rotate(x, ry);
}
}
pushUp(x);
if(goal==) root=x;
} int Select(int pos) {
int u=root;
pushDown(u);
while(T[T[u].son[]].Size!=pos) {
if(pos<T[T[u].son[]].Size) u=T[u].son[];
else {
pos-=T[T[u].son[]].Size+;
u=T[u].son[];
}
pushDown(u);
}
return u;
} void update(int L, int R, int val) {
int u=Select(L-), v=Select(R+);
Splay(u, );
Splay(v, u);
T[T[v].son[]].Max+=val;
T[T[v].son[]].val+=val;
T[T[v].son[]].add+=val;
} void Reverse(int L, int R) {
int u=Select(L-), v=Select(R+);
Splay(u, );
Splay(v, u);
T[T[v].son[]].rev^=;
} int query(int L, int R) {
int u=Select(L-), v=Select(R+);
Splay(u, );
Splay(v, u);
return T[T[v].son[]].Max;
} int build(int L, int R) {
if(L>R) return ;
if(L==R) return L;
int mid=(L+R)>>, sL, sR;
T[mid].son[]=sL=build(L, mid-);
T[mid].son[]=sR=build(mid+, R);
fa[sL]=fa[sR]=mid;
pushUp(mid);
return mid;
} void init(int n) {
T[].init(-INF), T[].init(-INF), T[n+].init(-INF);
for(int i=; i<=n+; i++) T[i].init();
root=build(, n+), fa[root]=;
fa[]=, T[].son[]=root, T[].Size=;
}
}; Splay_Tree hehe; int main() {
int n, m;
scanf("%d%d", &n, &m);
hehe.init(n);
for(int i=, a, b, c, d; i<m; i++) {
scanf("%d", &a);
if(a==) {
scanf("%d%d%d", &b, &c, &d);
hehe.update(b, c, d);
}
else if(a==) {
scanf("%d%d", &b, &c);
hehe.Reverse(b, c);
}
else {
scanf("%d%d", &b, &c);
printf("%d\n", hehe.query(b, c));
}
}
return ;
}
BZOJ 1251