BZOJ4364: [IOI2014]wall砖墙(线段树)

题意

题目链接

sol

一个显然的思路是维护最大最小值以及最大最小值的覆盖标记。

https://paste.ubuntu.com/p/wxpbvzf6y2/

但实际上因为这题只需要输出最后的操作序列，那么我们只维护最大最小值的覆盖标记即可。

也就是对于每一个节点，把本层的最大最小值下传之后清除即可。

// luogu-judger-enable-o2
#include<bits/stdc++.h> 
#define ll long long 
using namespace std;
const int maxn = 8e6 + 10, inf = 1e9 + 10;
template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, k, opt[maxn], l[maxn], r[maxn], h[maxn];
#define ls k << 1
#define rs k << 1 | 1 
struct node {
    int l, r, mx, mn;
}t[maxn];
void psmin(int k, int v) {
    chmin(t[k].mx, v); chmin(t[k].mn, v);
}
void psmax(int k, int v) {
    chmax(t[k].mx, v); chmax(t[k].mn, v);
}
void pushdown(int k) {
    if(t[k].mn != inf)  psmin(ls, t[k].mn), psmin(rs, t[k].mn), t[k].mn = inf;
    if(t[k].mx != -inf) psmax(ls, t[k].mx), psmax(rs, t[k].mx), t[k].mx = -inf;
}
void build(int k, int ll, int rr) {
    t[k].l = ll; t[k].r = rr; t[k].mn = inf; t[k].mx = -inf; 
    if(ll == rr) return ;
    int mid = ll + rr >> 1;
    build(ls, ll, mid); 
    build(rs, mid + 1, rr);
}
void int(int k, int ll, int rr, int v, int opt) {
    if(ll <= t[k].l && t[k].r <= rr) {
        opt == 2 ? psmin(k, v) : psmax(k, v);
        return ;
    }
    pushdown(k);
    int mid = t[k].l + t[k].r >> 1;
    if(ll <= mid) int(ls, ll, rr, v, opt);
    if(rr  > mid) int(rs, ll, rr, v, opt);
}
void dfs(int k) {
    if(t[k].l == t[k].r) {printf("%d\n", max(0, min(t[k].mn, t[k].mx)));return ;}
    pushdown(k);
    dfs(ls); dfs(rs);
}
signed main() {
    //freopen("a.in", "r", stdin);
    n = read(); k = read();
    build(1, 1, n);
    for(int i = 1; i <= k; i++) {
        int opt = read(), l = read() + 1, r = read() + 1, h = read();
        if(opt == 1) int(1, l, r, h, 1);
        else int(1, l, r, h, 2);//çø¼äè¡min 
    }
    dfs(1);
    return 0;
}
/*
6 3
1 0 4 9240
1 3 4 564
2 0 1 9249

6 3
1 1 5 9240
1 4 5 564
2 1 2 9249
*/