变成同色
题目描述
给定一个长度为 N 的整数序列 A=(A1,A2,…,AN)。请依次处理 Q 次查询。
查询分为以下两种:
- 类型 1:
1 i x,把 Ai 改为 x。
- 类型 2:
2 l r,假设 Al,Al+1,…,Ar 中的每个 −1 都可以替换为任意正整数。如果能把 Al,Al+1,…,Ar 全部变成相同的值,输出 Yes,否则输出 No。
输入格式
输入第一行为两个整数 N,Q。
第二行为 N 个整数 A1,A2,…,AN。
接下来 Q 行,第 i 行表示第 i 次查询,格式为以下两种之一:
输出格式
对于每次类型 2 的查询,输出一行 Yes 或 No。
8 9
5 -1 3 -1 2 3 4 5
2 3 6
1 5 -1
2 3 6
1 7 5
2 7 8
2 1 8
1 3 5
1 6 -1
2 1 8
No
Yes
Yes
No
Yes
样例 1 解释
初始时 A=(5,−1,3,−1,2,3,4,5)。
第 1 次查询为类型 2,询问的子段是 (3,−1,2,3),无法把它们全部变成相同的值,因此输出 No。
第 2 次查询为类型 1,把 A5 改为 −1,此时 A=(5,−1,3,−1,−1,3,4,5)。
第 3 次查询为类型 2,询问的子段是 (3,−1,−1,3),可以把它们全部变成相同的值,因此输出 Yes。
数据范围
对于所有测试数据,保证:
- 1≤N,Q≤3×105;
- −1≤Ai≤106,且 Ai=0;
- 类型 1 的查询满足 1≤i≤N,−1≤x≤106,且 x=0;
- 类型 2 的查询满足 1≤l≤r≤N;
- 所有输入值均为整数。
子任务
本题共 20 个测试点,按测试点计分:
| 测试点 |
分值 |
每个测试点 |
特殊性质 |
| 1∼6 |
30 |
5 |
N,Q≤2000 |
| 7∼12 |
N,Q≤5×104 |
| 13∼20 |
40 |
无特殊限制 |
每个测试点单独评分,全部测试点的得分之和即为本题得分。