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