题解：P6794 [SNOI2020] 水池

· · 题解

思路

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

为了方便起见，我们把每个水池和挡板都看成一个元素，于是我们需要维护一个长为 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，再执行 ltag_x 和 rtag_x。

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

修改直接打标记（灌水要先线段树二分确定要修改的区间）即可。查询时，某个水池的高度即为 \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;
}