分数: 366 分
问题陈述
高桥管理 N 智能手机。智能手机的编号从 1 to N,以及智能手机的初始电池电量 i (1 \leq i \leq N) is S_i.
这些智能手机通过接收应用通知来消耗电池。有一天, Q 通知事件按顺序发生 1-st 到 Q-th。在 j-th (1 \leq j \leq Q) 通知事件,每台编号介于 L_j 和 R_j 包容性减少 1。然而,电池电量为 0 仍为 0。也就是说,如果通知事件所针对的智能手机的电池电量是 b,那么 b 更改为 \max(b - 1,\ 0).
在所有通知事件完成后查找每部智能手机的最终电池电量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
- 所有输入均为整数
输入
N Q S_1 S_2 \ldots S_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 第一行包含一个整数 N 代表智能手机的数量和一个整数 Q 表示通知事件的数量,以空格分隔。
- 第二行包含整数 S_1, S_2, \ldots, S_N 代表每部智能手机的初始电池电量,以空格分隔。
- 在下面 Q 行, j第行 (1 \leq j \leq Q) 包含整数 L_j 和 R_j 代表目标智能手机号码的范围 j-第一个通知事件,以空格分隔。
输出
在所有通知事件完成后,按智能手机的顺序打印所有智能手机的电池电量 1 to N,用空格分隔,在一行上。在末尾添加换行符。
示例输入 1
5 3 10 5 3 8 2 1 3 2 4 3 5
示例输出 1
9 3 0 6 1
示例输入 2
4 5 3 1 4 2 1 2 1 2 2 3 3 4 1 4
示例输出 2
0 0 1 0
示例输入 3
10 8 100 0 5 20 3 15 8 0 12 7 1 5 3 7 2 6 5 10 1 10 6 8 4 4 1 3
示例输出 3
97 0 0 15 0 10 4 0 10 5