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