Description
网上有许多题，就是给定一个序列，要你支持几种操作：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。
Input
第一行两个整数N，M。M为操作个数。 以下M行，每行最多四个整数，依次为K，L，R，V。K表示是第几种操作，如果不是第1种操作则K后面只有两个数。
Output
对于每个第3种操作，给出正确的回答。
Sample Input
4 4
1 1 3 2
1 2 4 -1
2 1 3
3 2 4
Sample Output
2
HINT
N<=50000，M<=100000。
题解
n+2： 如果要处理的范围是[1,xxx]，那就要把一个比1小的点转到根；如果范围是[xxx,n],就要把n+1转到r的父节点。
因为可能有负值，所以mx[0] = -inf
#include<cstdio> #include<algorithm> #define inf 0x7fffffff using namespace std; const int N = 50010; int rev[N],tag[N],id[N],mx[N],fa[N],w[N],size[N]; int c[N][2]; int n,m,opt,l,r,rt,v; void updata(int x) { int l = c[x][0], r = c[x][1]; size[x] = size[l] + size[r] +1; mx[x] = max(mx[l],mx[r]); mx[x] = max(mx[x],w[x]); } void build(int l,int r,int f) { if (l > r) return; int mid = (l+r) >> 1, now = id[mid], last = id[f]; if (l == r) { size[l] = 1; tag[l] = rev[l] = 0; fa[l] = last; if (l < f) c[last][0] = now; else c[last][1] = now; return; } build(l,mid-1,mid); build(mid+1,r,mid); fa[now] = last; updata(now); if (mid < f) c[last][0] = now; else c[last][1] = now; } void rotate(int x,int &k) { int y = fa[x], z = fa[y], l, r; if (c[y][0] == x) l = 0; else l = 1; r = l^1; if (y == k) k = x; else { if (c[z][0] == y) c[z][0] = x; else c[z][1] = x; } fa[x] = z; fa[y] = x; fa[c[x][r]] = y; c[y][l] = c[x][r]; c[x][r] = y; updata(y); updata(x); } void splay(int x,int &k) { while (x != k) { int y = fa[x],z = fa[y]; if (y != k) { if ((c[y][0] == x)^(c[z][0] == y)) rotate(x,k); else rotate(y,k); } rotate(x,k); } } void pushdown(int x) { int l = c[x][0], r = c[x][1]; if (rev[x]) { rev[l] ^= 1; rev[r] ^= 1; rev[x] = 0; swap(c[x][0],c[x][1]); } if (tag[x]) { if (l) tag[l] += tag[x], mx[l] += tag[x], w[l] += tag[x]; if (r) tag[r] += tag[x], mx[r] += tag[x], w[r] += tag[x]; tag[x] = 0; } } int find(int &k,int rk) { pushdown(k); int l = c[k][0], r = c[k][1]; if (size[l]+1 == rk) return k; if (size[l] >= rk) return find(l,rk); return find(r,rk-size[l]-1); } void add(int l,int r,int v) { int x = find(rt,l), y = find(rt,r+2); splay(x,rt); splay(y,c[x][1]); int z = c[y][0]; tag[z] += v; mx[z] += v; w[z] += v; } void rever(int l,int r) { int x = find(rt,l), y = find(rt,r+2); splay(x,rt); splay(y,c[x][1]); int z = c[y][0]; rev[z] ^= 1; } int solvemx(int l,int r) { int x = find(rt,l), y = find(rt,r+2); splay(x,rt); splay(y,c[x][1]); int z = c[y][0]; return mx[z]; } int main() { scanf("%d%d",&n,&m); mx[0] = -inf; for (int i = 1; i <= n+2; i++) id[i] = i; build (1,n+2,0); rt = (n+3) >> 1; for (int i = 1; i <= m ;i++) { scanf("%d%d%d",&opt,&l,&r); switch (opt) { case 1: scanf("%d",&v); add(l,r,v); break; case 2: rever(l,r); break; case 3: printf("%d ",solvemx(l,r)); break; } } }