← 返回题目列表

AtCoder · past202010_l

L. 公寓装修

中文机器翻译题面 查看原题

分数: 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