有 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 的。