33OJ
登录 注册

#ABC484F. 变成同色

变成同色

变成同色

题目描述

给定一个长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)。请依次处理 QQ 次查询。

查询分为以下两种:

  • 类型 1:1 i x,把 AiA_i 改为 xx。
  • 类型 2:2 l r,假设 Al,Al+1,…,ArA_l,A_{l+1},\ldots,A_r 中的每个 −1-1 都可以替换为任意正整数。如果能把 Al,Al+1,…,ArA_l,A_{l+1},\ldots,A_r 全部变成相同的值,输出 Yes,否则输出 No。

输入格式

输入第一行为两个整数 N,QN,Q。

第二行为 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

接下来 QQ 行,第 ii 行表示第 ii 次查询,格式为以下两种之一:

  • 1 i x
  • 2 l r

输出格式

对于每次类型 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)A=(5,-1,3,-1,2,3,4,5)。

第 11 次查询为类型 2,询问的子段是 (3,−1,2,3)(3,-1,2,3),无法把它们全部变成相同的值,因此输出 No。

第 22 次查询为类型 1,把 A5A_5 改为 −1-1,此时 A=(5,−1,3,−1,−1,3,4,5)A=(5,-1,3,-1,-1,3,4,5)。

第 33 次查询为类型 2,询问的子段是 (3,−1,−1,3)(3,-1,-1,3),可以把它们全部变成相同的值,因此输出 Yes。

数据范围

对于所有测试数据,保证:

  • 1≤N,Q≤3×1051 \le N,Q \le 3 \times 10^5;
  • −1≤Ai≤106-1 \le A_i \le 10^6,且 Ai≠0A_i \neq 0;
  • 类型 1 的查询满足 1≤i≤N1 \le i \le N,−1≤x≤106-1 \le x \le 10^6,且 x≠0x \neq 0;
  • 类型 2 的查询满足 1≤l≤r≤N1 \le l \le r \le N;
  • 所有输入值均为整数。

子任务

本题共 20 个测试点,按测试点计分:

测试点 分值 每个测试点 特殊性质
1∼61 \sim 6 3030 55 N,Q≤2000N, Q \le 2000
7∼127 \sim 12 N,Q≤5×104N, Q \le 5 \times 10^4
13∼2013 \sim 20 4040 无特殊限制

每个测试点单独评分,全部测试点的得分之和即为本题得分。