思路
这个问题的核心在于“连续”、“非空”以及“乘积均相同”这几个条件。
-
乘积相同的含义
数组中的元素只有 1 和 2。任何一个子数组的乘积都是 2 的某个次幂（包括 20=1）。要想让 z 个子数组的乘积都相同，那么它们的乘积必然都等于同一个值 P。这个值 P 也必须是 2 的幂。
-
与 2 的数量挂钩
一个子数组的乘积由其中 2 的数量决定。如果一个子数组有 k 个 2，那么它的乘积就是 2k。因此，“所有子数组乘积相同”等价于“所有子数组包含的 2 的数量相同”。
P3730.第1题-数组划分
题目内容
Tk 的朋友给了他一个长度为 n 、仅由 {1,2 } 构成的数组 {a1,a2,...,an}。Tk 对这个数组很感兴趣，他将对数组进行 m 次操作。
每次操作给出三个整数 x,y,z ，含义如下：
-
先将 ax 修改为 y (其中 y∈{1,2});
-
修改之后，Tk 想知道是否可以将整个数组划分为恰好 z 个连续且非空的段，使得这 z 段的乘积均相同。
对于每次操作，请输出结果：若可以，输出 Yes ；否则输出 NO 。
注意：每次修改会影响数组的当前状态，并用于后续操作。
【名词解释】
划分为 z 段：选择 z−1 个切分点，将数组分成 z 个连续且非空的段，覆盖整个数组且两两不交。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦104) 代表数据组数，每组测试数据描述如下：
第一行输入两个整数 n,m(1≦n,m≦2×105) 分别表示数组长度与操作次数；
第二行输入 n 个整数 a1,a2,...,an(1≦ai≦2) ；
接下来 m 行，每行输入三个整数
x,y,z(1≦x≦n,1≦y≦2,1≦z≦n) ，表示一次操作。
除此之外，保证单个测试文件的 n 之和 、m 之和均不超过 2×105 。
输出描述
对于每组测试数据，输出 m 行。对每次操作，若可以完成所需划分，输出 Yes ，否则输出 No 。
样例1
输入
2
4 4
1 2 1 2
1 1 1
2 1 2
3 2 2
4 2 3
3 3
1 1 1
2 1 2
1 2 2
3 2 1
输出
Yes
No
Yes
No
Yes
No
Yes
说明
对于第一组数据，初始数组为 {1,2,1,2} 。
-
第一次操作后数组变为 {1,2,1,2} 可以分割为 {1,2,1,2} 满足条件输出 Yes 。
-
第二次操作后数组为 {1,1,1,2 } 无法分割为两个乘积相同子段。
