题解：P6794 [SNOI2020] 水池
流水行船CCD
·
·
题解
提供一种分块做法。
注意到 0 操作就是给从 x 左边第一个高度大于 h 挡板到 x 右边第一个高度小于 h 的挡板中间的水池高度赋值为 h。区间赋值，分块可以直接维护。
而 1 操作就是把每一个水池的高度和它到 x 水池中间最高挡板高度 chkmin。
注意到 1 操作是一个类似单调栈的结构，考虑分块去维护。
给每一个块打一个 lchk,rchk 标记，表示这个块的左侧/右侧有排水操作的影响需要更新，记录这些排水操作的排水点到当前块的边界最高挡板的高度最小值。
那么 1 操作的时候只需要把排水点所在块暴力修改，其他块直接打标记。
修改挡板高度时直接把对应块重构。查询一个点水深的时候直接把它所在的块标记下放，就可以查到正确值。
至于可持久化，由于本题可以离线，使用操作树+回滚可以维护，注意尽量节约使用空间，没必要放入回滚栈中的元素就不要放。
## code
为了图方便，实现的比较丑陋（比如找赋值区间使用线段树外二分）。
```cpp
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define ld cin
#define jyt cout
#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i)
#define clr(name, n) memset(name, 0, ((n) + 1) * sizeof(name[0]))
#define mem(name, v, n) memset(name, v, ((n) + 1) * sizeof(name[0]))
const int N = 2e5 + 7, B = 450;
const int inf = 1e9 + 7;
const int P = 998244353;
namespace JoKing { // JoKing 10:56 60~70pts
int n, W, q, a[N], h[N], lmx[N], rmx[N], bel[N], L[N], R[N], tage[N], lchk[N], rchk[N];
vector<int> G[N]; pair<int*, int> stc[50000000]; int Ans[N], top = 0;
struct Opera {int op, id, x, h;} c[N];
struct Node {
int lc, rc, mx;
#define ls(x) tr[x].lc
#define rs(x) tr[x].rc
} tr[N * 30]; int Rt[N], Trc = 0;
inline void blt(int &x, int l, int r) {
if (x = ++Trc, l == r) return void(tr[x].mx = h[l]);
int mid = (l + r) >> 1;
blt(ls(x), l, mid), blt(rs(x), mid + 1, r), tr[x].mx = max(tr[ls(x)].mx, tr[rs(x)].mx);
}
inline void upd(int &x, int l, int r, int now, int c) {
if (tr[++Trc] = tr[x], x = Trc, l == r) return void(tr[x].mx = c);
int mid = (l + r) >> 1;
(now <= mid ? upd(ls(x), l, mid, now, c) : upd(rs(x), mid + 1, r, now, c)), tr[x].mx = max(tr[ls(x)].mx, tr[rs(x)].mx);
}
inline int ask(int x, int l, int r, int L, int R) {
if (L <= l && r <= R) return tr[x].mx;
int mid = (l + r) >> 1, c = -1;
if (L <= mid) c = max(c, ask(ls(x), l, mid, L, R));
if (mid < R) c = max(c, ask(rs(x), mid + 1, r, L, R));
return c;
}
inline void pushtag(int Biden) {
if (tage[Biden] != -1 || lchk[Biden] != -1 || rchk[Biden] != -1) REP(i, L[Biden], R[Biden]) stc[++top] = {&a[i], a[i]};
if (tage[Biden] != -1) {REP(i, L[Biden], R[Biden]) a[i] = tage[Biden]; stc[++top] = {&tage[Biden], tage[Biden]}; tage[Biden] = -1;}
if (lchk[Biden] != -1) {REP(i, L[Biden], R[Biden]) a[i] = min(a[i], max(lchk[Biden], lmx[i])); stc[++top] = {&lchk[Biden], lchk[Biden]}; lchk[Biden] = -1;}
if (rchk[Biden] != -1) {REP(i, L[Biden], R[Biden]) a[i] = min(a[i], max(rchk[Biden], rmx[i])); stc[++top] = {&rchk[Biden], rchk[Biden]}; rchk[Biden] = -1;}
}
inline void rebuild(int Biden) {
if (lmx[L[Biden]] != 0) stc[++top] = {&lmx[L[Biden]], lmx[L[Biden]]};
lmx[L[Biden]] = 0;
REP(i, L[Biden] + 1, R[Biden]) {
if (lmx[i] != max(lmx[i - 1], h[i - 1])) stc[++top] = {&lmx[i], lmx[i]};
lmx[i] = max(lmx[i - 1], h[i - 1]);
}
if (rmx[R[Biden]] != h[R[Biden]]) stc[++top] = {&rmx[R[Biden]], rmx[R[Biden]]};
rmx[R[Biden]] = h[R[Biden]];
PER(i, R[Biden] - 1, L[Biden]) {
if (rmx[i] != max(rmx[i + 1], h[i])) stc[++top] = {&rmx[i], rmx[i]};
rmx[i] = max(rmx[i + 1], h[i]);
}
}
inline int findl(int Rt, int now, int c) {
int L = 1, R = now, Res = 0;
while (L <= R) {
int mid = (L + R) >> 1, w = ask(Rt, 1, n, mid, now);
if (w >= c) L = mid + 1, Res = mid;
else R = mid - 1;
} return Res;
}
inline int findr(int Rt, int now, int c) {
int L = now, R = n, Res = n;
while (L <= R) {
int mid = (L + R) >> 1, w = ask(Rt, 1, n, now, mid);
if (w >= c) R = mid - 1, Res = mid;
else L = mid + 1;
} return Res;
}
inline void TAGE(int l, int r, int c) {
int S = bel[l], T = bel[r];
if (S == T) {pushtag(S); REP(i, l, r) (a[i] != c && (stc[++top] = {&a[i], a[i]}, 1)), a[i] = c; return;}
pushtag(S), pushtag(T);
REP(i, l, R[S]) (a[i] != c && (stc[++top] = {&a[i], a[i]}, 1)), a[i] = c;
REP(i, S + 1, T - 1) {
(lchk[i] != -1 && (stc[++top] = {&lchk[i], lchk[i]}, 1));
(rchk[i] != -1 && (stc[++top] = {&rchk[i], rchk[i]}, 1));
(tage[i] != c && (stc[++top] = {&tage[i], tage[i]}, 1));
lchk[i] = rchk[i] = -1, tage[i] = c;
}
REP(i, L[T], r) (a[i] != c && (stc[++top] = {&a[i], a[i]}, 1)), a[i] = c;
}
inline void LCHK(int now) {
int Trump = bel[now], mx = h[now]; stc[++top] = {&a[now], a[now]}, a[now] = 0;
REP(i, now + 1, R[Trump]) (a[i] != min(a[i], mx) && (stc[++top] = {&a[i], a[i]}, 1)), a[i] = min(a[i], mx), mx = max(mx, h[i]);
REP(i, Trump + 1, W) {
if (lchk[i] != -1 && lchk[i] <= mx) break;
(lchk[i] != mx && (stc[++top] = {&lchk[i], lchk[i]}, 1));
lchk[i] = mx, mx = max(mx, rmx[L[i]]);
}
}
inline void RCHK(int now) {
int Trump = bel[now], mx = 0; stc[++top] = {&a[now], a[now]}, a[now] = 0;
PER(i, now - 1, L[Trump]) mx = max(mx, h[i]), (a[i] != min(a[i], mx) && (stc[++top] = {&a[i], a[i]}, 1)), a[i] = min(a[i], mx);
PER(i, Trump - 1, 1) {
if (rchk[i] != -1 && rchk[i] <= mx) break;
(rchk[i] != mx && (stc[++top] = {&rchk[i], rchk[i]}, 1));
rchk[i] = mx, mx = max(mx, rmx[L[i]]);
}
}
inline void dfs(int x, bool need = false) {
need |= (G[x].size() > 1);
for (int i : G[x]) {
int his = top;
if (c[i].op == 0) {
if (pushtag(bel[c[i].x]), c[i].h > a[c[i].x]) TAGE(findl(Rt[i], c[i].x - 1, c[i].h) + 1, findr(Rt[i], c[i].x, c[i].h), c[i].h);
} else if (c[i].op == 1) {
pushtag(bel[c[i].x]), LCHK(c[i].x), RCHK(c[i].x);
} else if (c[i].op == 2) {
stc[++top] = {&h[c[i].x], h[c[i].x]};
h[c[i].x] = c[i].h, pushtag(bel[c[i].x]), rebuild(bel[c[i].x]);
} else {
pushtag(bel[c[i].x]), Ans[i] = a[c[i].x];
}
if (!need) top = 0;
dfs(i, need);
while (top != his) *stc[top].first = stc[top].second, --top;
}
}
signed main() { bool flag = true, CZXD = true;
ld >> n >> q, h[n] = inf;
REP(i, 1, n - 1) ld >> h[i];
REP(i, 1, q) ld >> c[i].op >> c[i].id >> c[i].x, ((c[i].op % 2 == 0) && (ld >> c[i].h, 1)), flag &= (c[i].id == i - 1), CZXD &= (c[i].op != 1);
blt(Rt[0], 1, n);
REP(i, 1, q) G[c[i].id].emplace_back(i), Rt[i] = Rt[c[i].id], (c[i].op == 2 && (upd(Rt[i], 1, n, c[i].x, c[i].h), 1));
for (int l = 1, r = min(n, B); l <= n; l += B, r = min(n, r + B)) fill(bel + l, bel + r + 1, ++W), L[W] = l, R[W] = r, tage[W] = lchk[W] = rchk[W] = -1;
REP(i, 1, W) rebuild(i);
top = 0, dfs(0);
REP(i, 1, q) if (c[i].op == 3) jyt << Ans[i] << '\n';
return 0;
}
}
signed main() { // 400mb 0.9s
#ifdef WYY
freopen("water3.in", "r", stdin);
freopen("water.out", "w", stdout);
#else
// freopen("water3.in", "r", stdin);
// freopen("water.out", "w", stdout);
#endif
JoKing::main();
#ifdef WYY
// while(true);
#endif
return 0;
}
```