P4560 [IOI 2014] 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\sim n-1$**。 接下来 $k$ 行每行包含 $4$ 个整数 $t, L, R, h$，若 $t = 1$ 则表明为 Add 操作，若 $t = 2$ 则表明为 Remove 操作。$L, R, h$ 的含义见题目描述。

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

- 子任务 #1（8 分）：满足 $1 \leq n \leq 10^4$，$1 \leq k \leq 5\times 10^3$； - 子任务 #2（24 分）：满足 $1 \leq n \leq 10^5$，$ 1 \leq k \leq 5\times 10^5$，全部增加操作均在全部移除操作之前； - 子任务 #3（29 分）：满足 $1 \leq n \leq 10^5$，$ 1 \leq k \leq 5\times 10^5$； - 子任务 #4（39 分）：满足 $1 \leq n \leq 2\times 10^6$，$1 \leq k \leq 5\times 10^5$。 所有操作的高度 $h$ 满足 $0 \leq h \leq 10^5$。