有 n 个水箱，每个水箱有初始一定的水量，用一个整数 ai 表示，水箱的高度足够高。
scx 将会进行以下五种操作：
第一行两个正整数 n, m，表示水箱个数和操作次数。
第二行 n 个正整数，依次描述每个水箱的水量。
接下来的 m 行，每行第一个数 ti 表示操作类型：
如果 ti ≤ 3，则接下来三个整数 li, ri, xi，意义如描述所述。
如果 ti > 3，则接下来一个整数 yi，意义如描述所述。
对于每个 ti > 3，输出一个整数回答询问。
这题简直就是一道毒瘤题...(如果想直接看题解，点击此处)
(scx: 为什么呢？)
第一，题面毒瘤。
上面其实是我简化的题面，原文的题面简直让我吐血。
我现在复制几句话，你就可以看到它有多毒瘤：
"水箱顶部和底部都有一个接口，水的电阻率为 1 Ω·m 。"。
"有一个导电浮标浮在水面上，通过导线与水箱顶的接口相连。"
"操作4: 在第 y 个水箱的上下方接口处接上一个电动势为 1 V 的电源，电源没有内阻，Picks博士会测量出通过电源的电流大小，之后撤去该电源。"
"1、欧姆定律：，其中 I, U, R 分别代表电流、电压和电阻。"
"2、电阻率公式：，其中 R, ρ, L, S 分别代表电阻、电阻率、电阻长度、横截面积。"
"对于每个 ti，输出一个整数表示通过电源的电流大小的倒数(单位为 A?1)，如果电流为无穷大则输出0。"
(scx: 这要说的不就是询问第 y 个水箱的水量么？)
这就是我说这题毒瘤的原因，还有一个毒瘤详见"坑"部分。
现在开始题解。
首先，这道题用线段树不解释，但是坑人的其实就是操作 2。
操作 2 是让所有水箱的水量减少 x，并对 0 取 max。
所以可以想到，每次操作后，每个水箱的水量一定可以用下式表示(x0 为最初水量)：x = max(x0 + a, b)。
所以，线段树中每个底层节点可以记录这样一对值: (a, b)，询问时直接输出max(x + a, b)(x 为水量)。
当然，在修改的时候可以在根上修改，不过要立刻下传标记。
接下来解释操作 1 ~ 4 如何实现：
假设当前的值为 x = max(x0 + a, b)。
在操作 1 之后(假设增加 c)，会变为 x = max(x0 + a + c, b + c)
在操作 2 之后(假设减少 c)，会变为 x = max(x0 + a - c, b - c, 0) = max(x0 + (a - c), max(b - c, 0))
然而操作 3，可以转化为"减少 INF 后，再增加 x"(这个 INF 非常玄学，见"坑")
(scx: 那么 push_down 呢？)
在 push_down 中，假设父节点为 x = max(x0 + a, b)，子节点为 x = max(x0 + c, d)(左右都一样)
则子节点会更新为 x = max(max(x0 + c, d) + a, b) = max(x0 + c + a, d + a, b) = max(x0 + (c + a), max(d + a, b))。
可见，所有操作都会保持下式的形式：x = max(x0 + a, b)。
(scx: 那么历史最值呢？)
这个其实不难。假设某一个节点出现过 k 个(a, b)对，记作 (a1, b1), (a2, b2), ..., (ak, bk)，则 xmax = max(max(x0 + a1, b1), max(x0 + a2, b2), ..., max(x0 + ak, bk))因此，我们仅需记录 amax 为所有 ai 的最大值，bmax 为所有 bi 的最大值。询问时直接输出max(x + amax, bmax)(x 为水量)。
#include <bits/stdc++.h>
#define N 512202
#define INF 0x2c9d526cd03581ell
using namespace std;
typedef long long ll;
template <typename T>
struct ST{
int sz;
struct node{int l, r; T v0, v1, m0, m1;}*x;
ST (int size = 100){x = 0; resize(size);}
~ST (){delete(x);}
void resize(int size){sz = size; if(x) delete(x); x = new node[sz << 2]; memset(x, 0, (sz << 2) * sizeof(T));}
void init(){build(1, 1, sz);}
void add(int l, int r, T v){add(1, 1, sz, l, r, v);}
void sub(int l, int r, T v){sub(1, 1, sz, l, r, v);}
T qry(int h, T v){int id = find(1, 1, sz, h); return max(v + x[id].v0, x[id].v1);}
T his(int h, T v){int id = find(1, 1, sz, h); return max(v + x[id].m0, x[id].m1);}
//////////////////////////////////
inline void up(T &a, T b){a < b ? a = b : b;}
void build(int id, int L, int R){
x[id].v0 = x[id].v1 = x[id].m0 = x[id].m1 = 0;
if(L < R){
int M = L + R - 1 >> 1;
build(id << 1, L, M);
build(id << 1 | 1, M + 1, R);
}
}
void update(int id){
up(x[id].v0, -INF); up(x[id].v1, -INF);
up(x[id].m0, x[id].v0); up(x[id].m1, x[id].v1);
}
void push_down(int id, int Lc, int Rc){
up(x[Lc].m0, x[Lc].v0 + x[id].m0); up(x[Rc].m0, x[Rc].v0 + x[id].m0);
up(x[Lc].m1, max(x[id].m1, x[Lc].v1 + x[id].m0)); up(x[Rc].m1, max(x[id].m1, x[Rc].v1 + x[id].m0));
x[Lc].v0 += x[id].v0; x[Rc].v0 += x[id].v0;
x[Lc].v1 += x[id].v0; x[Rc].v1 += x[id].v0;
up(x[Lc].v1, x[id].v1); up(x[Rc].v1, x[id].v1);
x[id].v0 = x[id].v1 = x[id].m0 = x[id].m1 = 0;
update(Lc); update(Rc);
}
void add(int id, int L, int R, int ql, int qr, T v){
if(R < ql || qr < L) return;
if(ql <= L && R <= qr){x[id].v0 += v; x[id].v1 += v; update(id); return;}
int M = L + R - 1 >> 1, Lc = id << 1, Rc = Lc | 1;
push_down(id, Lc, Rc);
if(ql <= M) add(Lc, L, M, ql, qr, v);
if(qr > M) add(Rc, M + 1, R, ql, qr, v);
}
void sub(int id, int L, int R, int ql, int qr, T v){
if(R < ql || qr < L) return;
if(ql <= L && R <= qr){x[id].v0 -= v; x[id].v1 -= v; up(x[id].v1, 0); update(id); return;}
int M = L + R - 1 >> 1, Lc = id << 1, Rc = Lc | 1;
push_down(id, Lc, Rc);
if(ql <= M) sub(Lc, L, M, ql, qr, v);
if(qr > M) sub(Rc, M + 1, R, ql, qr, v);
}
int find(int id, int L, int R, int h){
if(L == R) return id;
int M = L + R - 1 >> 1, Lc = id << 1, Rc = Lc | 1;
push_down(id, Lc, Rc);
if(h <= M) return find(Lc, L, M, h);
if(h > M) return find(Rc, M + 1, R, h);
}
};
int n, q, i;
int a[N];
int ch, l, r, h;
ll x;
ST <ll> s;
int main(){
scanf("%d%d", &n, &q);
s.resize(n);
for(i = 1; i <= n; i++)
scanf("%d", a + i);
s.init();
for(; q; q--){
switch(scanf("%d", &ch), ch){
case 1:
scanf("%d%d%lld", &l, &r, &x);
s.add(l, r, x);
break;
case 2:
scanf("%d%d%lld", &l, &r, &x);
s.sub(l, r, x);
break;
case 3:
scanf("%d%d%lld", &l, &r, &x);
s.sub(l, r, INF);
s.add(l, r, x);
break;
case 4:
scanf("%d", &h);
printf("%lld\n", s.qry(h, (ll)a[h]));
break;
case 5:
scanf("%d", &h);
printf("%lld\n", s.his(h, (ll)a[h]));
break;
}
}
return 0;
}
看到代码第三行，看到这么一个奇怪的 16 进制数，你就可以感觉到这道题满满的恶意……
话说它的 10 进制形式是 200926021019719710，感觉非常玄学有木有？
其实这题官方的数据还是比较良心的，也就是说到 97 分还是写得比较快的，主要是这么几个坑：
坑1：开 long long(其实我已经习惯啦)。
坑2：a 和 b(本例为 v0, v1)的变化情况要清晰，它们的变化是不同的(从题解中可以看出来)，所以不要一股的 Ctrl + C, Ctrl + V。
然后交一发就到了 97 分。然后看一下这个 hack 的数据：
1 500000 1000000000 1 1 1 1000000000 1 1 1 1000000000 1 1 1 1000000000 1 1 1 1000000000 1 1 1 100000...
273070795280291
wrong answer 1st numbers differ - expected: '1', found: '273070795280291'
(scx: 这数据看起来好奇怪！为什么会输出这么大的数？)
就一个水箱，不停地往里面加 109，加 5×105 次，可能最后有一个操作 3(清零)。
那么多次加好后，水箱里的水量大约为 5×1014，这个时候清零操作是减一个 INF，然而当时的 INF 为 226928204719710 ≈ 2.27×1014，居然连水量都不到，所以减一个 INF 后在询问，就会输出一个比较大的值了(本例约为 2.73×1014)，和实际的输出基本一样。
于是这就找到原因了，把 INF 调大了一点。
(scx: 然后你过了吗？)
然后又挂了，甚至 97 都没了……后来发现，这是因为 INF 太大，两个 -INF 相加在 long long 范围内溢出，成了一个大正数，和 -INF 比较取 max 就失效了，所以连标准数据都测成 1019 这个数量级的数了。
所以调来调去，INF 不能太大，也不能太小，然后调了 7 次终于过了(现在的 INF)。
这就是第二个毒瘤。第一个已经说了，是出题人的那个鬼畜的题目描述，莫名其妙还很突兀的加一些电学知识，第二个不是原题的原因，是那个 hack 的人闲的蛋疼来卡程序的 INF 的。