题目详情题解（0）讨论（0）提交记录（0）

AT_past202010_l.マンションの改築

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

维护一个长为 nn 的数组 hh。支持以下三种操作：

  • 1 v：将数组中所有下标为奇数的元素全部加上 vv。
  • 2 v：将数组中所有下标为偶数的元素全部加上 vv。
  • 3 u v：将 huh_u 加上 vv。

请在每次操作结束后，输出一行一个整数，表示：对于所有满足 1≤i<n1 \le i \lt n 的整数 ii，有多少个满足在本次操作后 hi=hi+1h_i=h_{i+1}？

输入格式

第一行为数组长度 nn 和操作次数 qq。

第二行为 nn 个整数，表示数列 hh。

接下来 qq 行每行一个操作，格式见题。

输出格式

输出 qq 行，第 ii 行输出的整数为在第 ii 次操作结束后，满足 1≤j<n1 \le j \lt n 且 hj=hj+1h_j=h_{j+1} 的整数 jj 的个数。

输入输出样例

  • 输入#1

    4 2
10 20 30 20
1 10
3 4 20

    输出#1

    1
2

  • 输入#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

说明/提示

数据规模与约定

对于全部测试点，数据保证：

  • 输入数值均为整数；
  • 2≤n≤2×1052 \le n \le 2 \times 10^5，1≤q≤2×1051 \le q \le 2 \times 10^5；
  • 1≤h,v≤1091 \le h,v \le 10^9，1≤u≤n1 \le u \le n。

输入解题思路，AI测评打分。不知道怎么写?

首页