题目链接：https://codeforces.com/contest/1912/attachments/download/23419/icpc-nerc-2023-statements.pdf
题意简述
相信大家都听说过经典的接雨水问题。给定 \(n\) 个数作为初始的地砖高度分布 \(a_i\)，\(q\) 次修改。
第 \(i\) 次修改由两个数 \(l_i, r_i\) 描述，所有 \([l_i, r_i]\) 区间内的地砖高度 \(+1\)。
在初始以及每次修改后，输出数组 \(a_i\) 能够接雨水的量。修改是在同一个数组上先后进行的，也就是之间存在影响。
题解（官解）
这题和南京M在题意、解法上有非常大的相似之处，可惜我赛时虽然很快联想到了这题，但还是没有想到转化后具体的做法。
与南京M相同，记 \(f_i, g_i\) 分别为前后缀最大值，则要求的就是 \(\sum\limits_{i=1}^n(\min(f_i, g_i) - a_i)\)。
在这一步转化后，这题与南京M相同，都有多种做法。一种方式是与南京官解相同，将其转化为 \(\sum\limits_{i=1}^n(f_i + g_i - a_i - \max\limits_{x \in a} x)\)。全局最大值的维护较容易，则只需要维护 \(f\) 和 \(g\) 的变化。
对此，官方解答给出了一个结论：一次操作至多只会使 \(f\) 数组产生一次区间 \(+1\)。其中，如果发生了修改，则修改的左端点是 \(l_i\) 及之后第一个满足 \(a_i \ge f_{l_i-1}\) 的点；修改一旦发生，就至少持续到 \(r_i\)，且在第一个 \(a_i > f_{r_i}\) 的点（不包含）结束。修改的左右端点都可以使用常规的线段树上算法，在 \(O(\log n)\) 时间内找到。对于 \(g\) 数组完全对称。
代码实现（C++）
#define int i64
struct segtree {
struct node {
int mx, lazy;
};
vector<node> tr;
segtree(int n) : tr(4 * n) {}
void build(int id, int l, int r, vector<int> &a) {
if (l == r) {
tr[id].mx = tr[id].lazy = a[l];
} else {
int mid = (l + r) >> 1;
build(2 * id, l, mid, a), build(2 * id + 1, mid + 1, r, a);
tr[id].mx = max(tr[2 * id].mx, tr[2 * id + 1].mx);
}
}
void pushdown(int id) {
int l = tr[id].lazy;
tr[id].lazy = 0;
tr[2 * id].mx += l;
tr[2 * id].lazy += l;
tr[2 * id + 1].mx += l;
tr[2 * id + 1].lazy += l;
}
void add(int id, int ql, int qr, int l, int r) {
if (ql <= l && r <= qr) {
tr[id].lazy++;
tr[id].mx++;
} else {
int mid = (l + r) >> 1;
pushdown(id);
if (ql <= mid) add(id * 2, ql, qr, l, mid);
if (qr > mid) add(id * 2 + 1, ql, qr, mid + 1, r);
tr[id].mx = max(tr[2 * id].mx, tr[2 * id + 1].mx);
}
}
int query(int id, int ql, int qr, int l, int r) {
if (ql > qr) return -1;
if (ql <= l && r <= qr) { return tr[id].mx; }
int mid = (l + r) >> 1;
pushdown(id);
int res = 0;
if (ql <= mid) res = max(res, query(id * 2, ql, qr, l, mid));
if (qr > mid) res = max(res, query(id * 2 + 1, ql, qr, mid + 1, r));
return res;
}
int first_gr(int id, int ql, int l, int r, int x, int &now_mx) {
if (r < ql) return -1;
if (ql <= l) {
int t = max(now_mx, tr[id].mx);
if (t <= x) {
now_mx = t;
return -1;
}
if (l == r) return l;
}
int mid = (l + r) >> 1;
pushdown(id);
int pos = first_gr(2 * id, ql, l, mid, x, now_mx);
if (pos != -1) return pos;
return first_gr(2 * id + 1, ql, mid + 1, r, x, now_mx);
}
};
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 2);
i64 res = 0;
{
int tmx = 0;
for (int i = n; i >= 1; i--) {
cin >> a[i];
tmx = max(tmx, a[i]);
res += tmx - a[i];
}
tmx = 0;
for (int i = 1; i <= n; i++) {
tmx = max(tmx, a[i]);
res += tmx;
}
}
segtree trf(n), trg(n);
trg.build(1, 1, n, a);
ranges::reverse(a);
trf.build(1, 1, n, a);
cout << res - n * trf.tr[1].mx << "\n";
while (q--) {
int l, r;
cin >> l >> r;
res -= (r + 1 - l);
int now_mx = 0,
posl = trf.first_gr(1, l, 1, n, trf.query(1, 1, l - 1, 1, n) - 1,
now_mx);
now_mx = 0;
int posr =
trf.first_gr(1, r + 1, 1, n, trf.query(1, 1, r, 1, n), now_mx);
if (posr == -1) posr = n + 1;
if (posl != -1 && posl <= r) { res += posr - posl; }
trf.add(1, l, r, 1, n);
tie(l, r) = pair(n + 1 - r, n + 1 - l);
now_mx = 0;
posl =
trg.first_gr(1, l, 1, n, trg.query(1, 1, l - 1, 1, n) - 1, now_mx);
now_mx = 0;
posr = trg.first_gr(1, r + 1, 1, n, trg.query(1, 1, r, 1, n), now_mx);
if (posr == -1) posr = n + 1;
if (posl != -1 && posl <= r) { res += posr - posl; }
trg.add(1, l, r, 1, n);
cout << res - n * trf.tr[1].mx << "\n";
}
}
#undef int