欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-25 19:57:52
题意 "题目链接" Sol 一个显然的思路是维护最大最小值以及最大最小值的覆盖标记。 https://paste.ubuntu.com/p/WXpBvzF6Y2/ 但实际上因为这题只需要输出最后的操作序列,那么我们只维护最大最小值的覆盖标记即可。 也就是对于每一个节点,把本层的最大最小值下传之后清除 ......

题意

题目链接

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
*/