分数: 6 点
警告
2020 年 11 月 8 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
有 N 公寓编号 1 通过 N,按此顺序站成一排。 最初,公寓的高度 i is h_i.
Q 操作将按顺序完成。的类型 i第一个操作表示为 t_{i},如下:
- If t_i=1:给定一个整数 v_i,增加每个奇数公寓的高度(Apartment 1, 3, ...)通过 v_i.
- If t_i=2:给定一个整数 v_i,增加每个偶数公寓的高度(公寓 2, 4, ...)通过 v_i.
- If t_i=2:给定整数 u_i 和 v_i, 增加公寓的高度 u_i 公寓 v_i.
对于每个操作,找到整数的数量 i 满意 1 \leq i < N 这样公寓的高度 i 和公寓 i+1 在操作结束时相等。
约束
- 输入中的所有值都是整数。
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq h_i, v_i \leq 10^9
- t_i is 1, 2,或 3.
- 1 \leq u_i \leq N
输入
输入由标准输入按以下格式给出:
N Q
h_1 h_2 \cdots h_N
\mathrm{Query}_{1}
\vdots
\mathrm{Query}_{Q}
在这里, \mathrm{Query}_{i} 是以下之一:
1 v_i
- 这表示该操作是通过 t_i=1.
2 v_i
- 这表示该操作是通过 t_i=2.
3 u_i v_i
- 这表示该操作是通过 t_i=3.
输出
打印 Q 行。的 q- 第行应包含整数的数量 i 满意 1 \leq i < N 这样公寓的高度 i 和公寓 i+1 的末尾相等 q第次操作。
示例输入 1
4 2 10 20 30 20 1 10 3 4 20
示例输出 1
1 2
- 最初,公寓的高度 1,2,3,4 是 分别为 10,20,30,20。
- 在 1-st操作,奇数公寓的高度发生变化,导致公寓的高度为 20,20,40,20.
- 现在有一个整数 i 这样公寓的高度 i 和公寓 i+1 相等: 1.
- 在 2-nd操作,Apartment的高度 4 变化,导致公寓的高度 20,20,40,40.
- 现在有两个整数 i 这样公寓的高度 i 和公寓 i+1 相等: 1,3.
示例输入 2
10 20 108 112 112 110 110 109 108 110 111 112 3 4 2 1 1 3 9 1 3 4 2 2 1 1 1 3 7 2 2 1 3 8 2 1 1 2 1 1 1 3 10 2 3 6 1 2 1 3 7 1 1 1 2 1 3 3 2 3 3 2
示例输出 2
2 2 1 1 2 1 0 3 3 0 3 0 0 0 4 3 1 3 3 2