题面：
网上有许多题，就是给定一个序列，要你支持几种操作：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种操作，给出正确的回答。
#include<bits/stdc++.h> using namespace std; const int M = 5e4+10; const int inf = 0x3f3f3f; int n,m,sz,rt; int c[M][2],fa[M],id[M],tag[M],v[M],mx[M],siz[M]; bool rev[M]; inline void pushup(int k){ int l = c[k][0],r = c[k][1]; mx[k] = max(max(mx[l],mx[r]),v[k]); siz[k] = siz[l] + siz[r] + 1; } void pushdown(int k){ int l = c[k][0],r = c[k][1],t = tag[k]; if(t){ tag[k] = 0; if(l) tag[l]+=t,mx[l]+=t,v[l]+=t; if(r) tag[r]+=t,mx[r]+=t,v[r]+=t; } if(rev[k]){ rev[k] = 0; rev[l]^=1; rev[r]^=1; swap(c[k][0],c[k][1]); } } 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; pushup(y); pushup(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); } } int Find(int k,int rk){ if(tag[k]||rev[k]) pushdown(k); int l = c[k][0],r = c[k][1]; if(siz[l]+1==rk) return k; else if(siz[l]>=rk) return Find(l,rk); else return Find(r,rk-siz[l]-1); } inline void update(int l,int r,int val){ 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] += val;v[z] += val; mx[z] += val; } inline 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; } inline void query(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]; printf("%d\n",mx[z]); } inline void build(int l,int r,int f){ if(l > r) return ; int now = id[l],last = id[f]; if(l == r){ fa[now] = last;siz[now]=1; if(l < f) c[last][0] = now; else c[last][1] = now; return ; } int mid = (l + r) >> 1; now = id[mid]; build(l,mid-1,mid); build(mid+1,r,mid); fa[now] = last; pushup(now); if(mid < f) c[last][0] = now; else c[last][1] = now; } int main() { mx[0] = -inf; scanf("%d%d",&n,&m); for(int i = 1;i <= n+2;i ++) id[i] = ++sz; build(1,n+2,0); rt = (n + 3) >> 1; for(int i = 1;i <= m;i ++){ int f,l,r,val; scanf("%d",&f); scanf("%d%d",&l,&r); if(f == 1) scanf("%d",&val),update(l,r,val); if(f == 2) rever(l,r); if(f == 3) query(l,r); } return 0; }
原文：https://www.cnblogs.com/kls123/p/10698932.html