[IOI2014] Wall 砖墙

题目背景

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

题目描述

给定一个长度为 $n$且初始值全为 $0$的序列。你需要支持以下两种操作: - Add $L, R, h$:将序列 $[L, R]$内所有值小于 $h$的元素都赋为 $h$,此时不改变高度大于 $h$的元素值 - Remove $L, R, h$:将序列 $[L, R]$内所有值大于 $h$的元素都赋为 $h$,此时不改变高度小于 $h$的元素值 你需要输出进行 $k$次上述操作之后的序列。

输入输出格式

输入格式


输入的第一行包含两个正整数 $n, k$,分别表示序列中元素的个数以及操作数量,注意:**序列下标编号为 $0$ ~ $n-1$**。 接下来 $k$行每行包含 $4$个整数 $t, L, R, h$,若 $t = 1$则表明为 Add 操作,若 $t = 2$则表明为 Remove 操作。 $L, R, h$的含义见题目描述。

输出格式


输出包含 $n$行,每行包含 $1$个整数。第 $i$行的整数表示 $k$次操作之后序列中编号为 $i - 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 000$; - 子任务#2(24分):满足 $1 \leq n \leq 100 000, 1 \leq k \leq 500 000$,全部增加操作均在全部移除操作之前; - 子任务#3(29分):满足 $1 \leq n \leq 100 000, 1 \leq k \leq 500 000$; - 子任务#4(39分):满足 $1 \leq n \leq 2 000 000, 1 \leq k \leq 500 000$。 所有操作的高度 $h$满足 $0 \leq h \leq 100 000$。