自动搬运

查看原文

来自洛谷，原作者为

	modfish_ 你指尖跃动的电光，事静电罢（恼

搬运于2025-08-24 22:24:03，当前版本为作者最后更新于2025-03-26 13:57:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

考虑灌水和放水分别代表着什么操作。

为了方便起见，我们把每个水池和挡板都看成一个元素，于是我们需要维护一个长为 $2n+1$ 的序列，它的奇数位是挡板，偶数位是水池。对每个偶数位维护 $a_{2i}$ 表示第 $i$ 个水池当前的高度，$h_{2i+1}$ 表示第 $i$ 个水池之后的挡板高度。特别地，$h_1=h_{2n+1}=\infty$。

灌水

显然，若要将第 $x$ 格水池灌到高度 $h$，需要找到最大的 $l<2x$ 和最小的 $r>2x$，满足 $h_l\ge h,h_r\ge h$，然后把 $l$ 和 $r$ 之间的水池的高度全部升到 $h$。

形式化地，对于 $\forall l<i<r, 2\mid i$ 进行操作 $a_i\leftarrow \max(a_i,h)$。

放水

若要将第 $x$ 格水池的水放空，$x$ 左边所有水池的水面都会降至其右边的最高的挡板的高度，右边的则会降至其左边的最高的挡板的高度。

形式化地，对于 $\forall 1\le i\le x,2\mid x$，进行操作 $a_i\leftarrow \min(a_i,\displaystyle\max_{i<j<x,2\nmid j}h_j)$。

那么如何实现这些操作呢？

考虑使用线段树维护这个长为 $2n+1$ 的序列。每个节点记录信息 $hmax_x$，表示这个区间内挡板的最大高度；以及 $mtag_x,ltag_x,rtag_x$，表示标记。具体地：

• $mtag_x$ 表示对 $x$ 所代表区间内所有水池的水面都抬高到 $mtag_x$ 高度。

• $ltag_x$ 表示对 $x$ 所代表区间内所有水池的水面，都降低至 $\max(ltag_x,suf)$ 高度。其中 $suf$ 表示该区间内某个水池在这个区间内对应后缀中最高的挡板高度。

• $rtag_x$ 同理，表示对 $x$ 所代表区间内所有水池的水面，都降低至 $\max(rtag_x,pre)$ 高度。其中 $pre$ 表示该区间内某个水池在这个区间内对应前缀中最高的挡板高度。

另外，对标记代表操作的执行顺序是：先执行 $mtag_x$，再执行 $ltag_x$ 和 $rtag_x$。

标记的下传是较为容易的：

• 对于 $mtag_{lc}$ 和 $mtag_{rc}$，直接和 $mtag_x$ 取 $\max$。

• 对于 $ltag_{lc}$ 和 $ltag_{rc}$，先和 $mtag_x$ 取 $\max$，然后 $ltag_{rc}$ 和 $ltag_x$ 取 $\min$，而 $ltag_{lc}$ 和 $\max(ltag_x,hmax_{rc})$ 取 $\min$。

• 对于 $rtag_{lc}$ 和 $rtag_{rc}$，和 $ltag$ 类似，可以自己推一下。

修改直接打标记（灌水要先线段树二分确定要修改的区间）即可。查询时，某个水池的高度即为 $\min(ltag,rtag,mtag)$。

至于可持久化，改用主席树即可。时间复杂度、空间复杂度均为 $O(q\log n)$。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e5 + 5;

int n, q;
int h[maxn];
namespace seg{
int lc[maxn * 100], rc[maxn * 100], hmax[maxn * 100], tot = 0;
int ltag[maxn * 100], rtag[maxn * 100], mtag[maxn * 100];
int create(int pr){
    tot ++, lc[tot] = lc[pr], rc[tot] = rc[pr], hmax[tot] = hmax[pr], ltag[tot] = ltag[pr], rtag[tot] = rtag[pr], mtag[tot] = mtag[pr];
    return tot;
}
void up(int x){
    hmax[x] = max(hmax[lc[x]], hmax[rc[x]]);
}
void down(int x){
    lc[x] = create(lc[x]), rc[x] = create(rc[x]);
    ltag[lc[x]] = max(ltag[lc[x]], mtag[x]), ltag[rc[x]] = max(ltag[rc[x]], mtag[x]);
    ltag[lc[x]] = min(ltag[lc[x]], max(ltag[x], hmax[rc[x]])), ltag[rc[x]] = min(ltag[rc[x]], ltag[x]);
    rtag[lc[x]] = max(rtag[lc[x]], mtag[x]), rtag[rc[x]] = max(rtag[rc[x]], mtag[x]);
    rtag[lc[x]] = min(rtag[lc[x]], rtag[x]), rtag[rc[x]] = min(rtag[rc[x]], max(rtag[x], hmax[lc[x]]));
    mtag[lc[x]] = max(mtag[lc[x]], mtag[x]), mtag[rc[x]] = max(mtag[rc[x]], mtag[x]);
    mtag[x] = 0, ltag[x] = rtag[x] = 1e9 + 100;
}
void build(int &x, int l, int r){
    x = create(0);
    if(l == r){
        if(l & 1){
            if(l == 1 || l == n * 2 + 1) hmax[x] = 1e9 + 100;
            else hmax[x] = h[l / 2];
        }
        return;
    }
    int mid = l + r >> 1;
    build(lc[x], l, mid), build(rc[x], mid + 1, r);
    up(x);
}
int findL(int x, int l, int r, int Q, int h){
    if(l == r){
        if(hmax[x] >= h) return l;
        else return 0;
    }
    if(r <= Q){
        if(hmax[x] < h) return 0;
        int mid = l + r >> 1;
        if(hmax[rc[x]] >= h) return findL(rc[x], mid + 1, r, Q, h);
        else return findL(lc[x], l, mid, Q, h);
    }
    int mid = l + r >> 1;
    if(Q <= mid) return findL(lc[x], l, mid, Q, h);
    else{
        int res = findL(rc[x], mid + 1, r, Q, h);
        if(res) return res;
        return findL(lc[x], l, mid, Q, h);
    }
}
int findR(int x, int l, int r, int Q, int h){
    if(l == r){
        if(hmax[x] >= h) return l;
        else return 0;
    }
    if(l >= Q){
        if(hmax[x] < h) return 0;
        int mid = l + r >> 1;
        if(hmax[lc[x]] >= h) return findR(lc[x], l, mid, Q, h);
        else return findR(rc[x], mid + 1, r, Q, h);
    }
    int mid = l + r >> 1;
    if(Q > mid) return findR(rc[x], mid + 1, r, Q, h);
    else{
        int res = findR(lc[x], l, mid, Q, h);
        if(res) return res;
        return findR(rc[x], mid + 1, r, Q, h);
    }
}
void water(int &x, int pr, int l, int r, int ql, int qr, int k){
    if(x == pr) x = create(pr);
    if(ql <= l && r <= qr){
        ltag[x] = max(ltag[x], k), rtag[x] = max(rtag[x], k), mtag[x] = max(mtag[x], k);
        return;
    }
    down(x);
    int mid = l + r >> 1;
    if(ql <= mid) water(lc[x], lc[pr], l, mid, ql, qr, k);
    if(qr > mid) water(rc[x], rc[pr], mid + 1, r, ql, qr, k);
}
int drainL(int &x, int pr, int l, int r, int Q, int rmax){
    if(x == pr) x = create(pr);
    if(r <= Q){
        ltag[x] = min(ltag[x], rmax);
        return max(rmax, hmax[x]);
    }
    down(x);
    int mid = l + r >> 1;
    if(Q <= mid) return drainL(lc[x], lc[pr], l, mid, Q, rmax);
    else return drainL(lc[x], lc[pr], l, mid, Q, drainL(rc[x], rc[pr], mid + 1, r, Q, rmax));
}
int drainR(int &x, int pr, int l, int r, int Q, int lmax){
    if(x == pr) x = create(pr);
    if(l >= Q){
        rtag[x] = min(rtag[x], lmax);
        return max(lmax, hmax[x]);
    }
    down(x);
    int mid = l + r >> 1;
    if(Q > mid) return drainR(rc[x], rc[pr], mid + 1, r, Q, lmax);
    else return drainR(rc[x], rc[pr], mid + 1, r, Q, drainR(lc[x], lc[pr], l, mid, Q, lmax));
}
void update(int &x, int pr, int l, int r, int id, int H){
    if(x == pr) x = create(pr);
    if(l == r){
        hmax[x] = H;
        return;
    }
    down(x);
    int mid = l + r >> 1;
    if(id <= mid) update(lc[x], lc[pr], l, mid, id, H);
    else update(rc[x], rc[pr], mid + 1, r, id, H);
    up(x);
}
int query(int &x, int pr, int l, int r, int id){
    if(x == pr) x = create(pr);
    if(l == r) return min(min(mtag[x], ltag[x]), rtag[x]);
    down(x);
    int mid = l + r >> 1;
    if(id <= mid) return query(lc[x], lc[pr], l, mid, id);
    else return query(rc[x], rc[pr], mid + 1, r, id);
}}
int rt[maxn];

int main(){
    scanf("%d %d", &n, &q);
    for(int i = 1; i < n; i ++) scanf("%d", &h[i]);
    seg::ltag[0] = seg::rtag[0] = 1e9 + 100;
    seg::build(rt[0], 1, n * 2 + 1);
    for(int j = 1; j <= q; j ++){
        int op, i, x, H;
        scanf("%d %d %d", &op, &i, &x);
        rt[j] = rt[i];
        if(op == 0){
            scanf("%d", &H);
            int l = seg::findL(rt[i], 1, n * 2 + 1, x * 2, H), r = seg::findR(rt[i], 1, n * 2 + 1, x * 2, H);
            seg::water(rt[j], rt[i], 1, n * 2 + 1, l + 1, r - 1, H);
        }else if(op == 1){
            seg::drainL(rt[j], rt[j], 1, n * 2 + 1, x * 2, 0), seg::drainR(rt[j], rt[j], 1, n * 2 + 1, x * 2, 0);
        }else if(op == 2){
            scanf("%d", &H);
            seg::update(rt[j], rt[i], 1, n * 2 + 1, x * 2 + 1, H);
        }else{
            printf("%d\n", seg::query(rt[j], rt[i], 1, n * 2 + 1, x * 2));
        }
    }
    return 0;
}