AT_abc484_f.Make them monochrome
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There is an integer sequence A=(A1,A2,…,AN) of length N.
Process the following Q queries.
Type 1 :
1 i x
Change Ai to x.
Type 2 :
2 l r
Suppose that each −1 contained in Al,Al+1,…,Ar can be replaced with an arbitrary positive integer. Print Yes if Al,Al+1,…,Ar can all be made equal, and No otherwise.
有一个长度为 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。
输入格式
The input is given from Standard Input in the following format, where Queryi denotes the i-th query:
N Q
A1 A2 … AN
Query1
Query2
⋮
QueryQ
输入从标准输入中按以下格式给出,其中 Queryi 表示第 i 个查询:
N Q
A1 A2 … AN
Query1
Query2
⋮
QueryQ
输出格式
Each time a query of type 2 is given, print the answer to that query in one line.
每次给出类型为 2 的查询时,在一行中输出该查询的答案。
输入输出样例
输入#1
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
输出#1
No Yes Yes No Yes
说明/提示
Sample 1 Explanation:
This input contains 9 queries.
Below, we explain the first 3 queries.
- Initially, A=(5,−1,3,−1,2,3,4,5).
- The 1-st query is of type 2, and the subarray in question is (3,−1,2,3). These cannot all be made equal by the operation in the problem statement, so print
No. - The 2-nd query is of type 1, and changes A5 to −1. As a result, A=(5,−1,3,−1,−1,3,4,5).
- The 3-rd query is of type 2, and the subarray in question is (3,−1,−1,3). These can all be made equal by the operation in the problem statement, so print
Yes.
Constraints
- All input values are integers.
- 1≤N,Q≤3×105
- −1≤Ai≤106
- Ai=0
- Queries of type 1 satisfy the following constraints:
- 1≤i≤N
- −1≤x≤106
- x=0
- Queries of type 2 satisfy the following constraints:
- 1≤l≤r≤N
样例 1 解释:
该输入包含 9 个查询。
下面解释前 3 个查询。
- 初始时,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
输入解题思路,AI测评打分。不知道怎么写?