洛谷P4560 Wall 砖墙

传送门

题目背景

原题为交互试题，但在此请提交完整程序。

题目描述

给定一个长度为 nn且初始值全为 00的序列。你需要支持以下两种操作：

Add L, R, hL,R,h：将序列 [L, R][L,R]内所有值小于 hh的元素都赋为 hh，此时不改变高度大于 hh的元素值
Remove L, R, hL,R,h：将序列 [L, R][L,R]内所有值大于 hh的元素都赋为 hh，此时不改变高度小于 hh的元素值
你需要输出进行 kk次上述操作之后的序列。

输入格式

输入的第一行包含两个正整数 n, kn,k，分别表示序列中元素的个数以及操作数量，注意：序列下标编号为 00 ~ n-1n−1。

接下来 kk行每行包含 44个整数 t, L, R, ht,L,R,h，若 t = 1t=1则表明为 Add 操作，若 t = 2t=2则表明为 Remove 操作。 L, R, hL,R,h的含义见题目描述。

输出格式

输出包含 nn行，每行包含 11个整数。第 ii行的整数表示 kk次操作之后序列中编号为 i - 1i−1的元素的值。

输入输出样例

输入 #1复制
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
输出 #1复制
0
0
0
39412
39412
39412
48623
48623
48623
48623
输入 #2复制
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
输出 #2复制
3
4
5
4
3
3
0
0
1
0

说明/提示

子任务#1（8分）：满足 1 \leq n \leq 10 000, 1 \leq k \leq 5 0001≤n≤10000,1≤k≤5000；
子任务#2（24分）：满足 1 \leq n \leq 100 000, 1 \leq k \leq 500 0001≤n≤100000,1≤k≤500000，全部增加操作均在全部移除操作之前；
子任务#3（29分）：满足 1 \leq n \leq 100 000, 1 \leq k \leq 500 0001≤n≤100000,1≤k≤500000；
子任务#4（39分）：满足 1 \leq n \leq 2 000 000, 1 \leq k \leq 500 0001≤n≤2000000,1≤k≤500000。
所有操作的高度 hh满足 0 \leq h \leq 100 0000≤h≤100000。

上代码：

#include 
#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() {
	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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61