AT_abc484_f.Make them monochrome

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

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

题目描述

There is an integer sequence A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N) of length NN.
Process the following QQ queries.

Type 11 :

1 ii xx

Change AiA_i to xx.

Type 22 :

2 ll rr

Suppose that each −1-1 contained in Al,Al+1,…,ArA_l,A_{l+1},\dots,A_r can be replaced with an arbitrary positive integer. Print Yes if Al,Al+1,…,ArA_l,A_{l+1},\dots,A_r can all be made equal, and No otherwise.

有一个长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N)。
请处理以下 QQ 个查询。

类型 11:

1 ii xx

将 AiA_i 修改为 xx。

类型 22:

2 ll rr

假设 Al,Al+1,…,ArA_l,A_{l+1},\dots,A_r 中每个 −1-1 都可被替换为任意一个正整数。若能使 Al,Al+1,…,ArA_l,A_{l+1},\dots,A_r 全部相等,则输出 Yes;否则输出 No。

输入格式

The input is given from Standard Input in the following format, where Queryi{\rm Query}_i denotes the ii-th query:

NN QQ
A1A_1 A2A_2 …\dots ANA_N
Query1{\rm Query}_1
Query2{\rm Query}_2
⋮\vdots
QueryQ{\rm Query}_Q

输入从标准输入中按以下格式给出,其中 Queryi{\rm Query}_i 表示第 ii 个查询:

NN QQ
A1A_1 A2A_2 …\dots ANA_N
Query1{\rm Query}_1
Query2{\rm Query}_2
⋮\vdots
QueryQ{\rm Query}_Q

输出格式

Each time a query of type 22 is given, print the answer to that query in one line.

每次给出类型为 22 的查询时,在一行中输出该查询的答案。

输入输出样例

  • 输入#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 99 queries.
Below, we explain the first 33 queries.

  • Initially, A=(5,−1,3,−1,2,3,4,5)A=(5,-1,3,-1,2,3,4,5).
  • The 11-st query is of type 22, and the subarray in question is (3,−1,2,3)(3,-1,2,3). These cannot all be made equal by the operation in the problem statement, so print No.
  • The 22-nd query is of type 11, and changes A5A_5 to −1-1. As a result, A=(5,−1,3,−1,−1,3,4,5)A=(5,-1,3,-1,-1,3,4,5).
  • The 33-rd query is of type 22, and the subarray in question is (3,−1,−1,3)(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×1051 \le N,Q \le 3 \times 10^5
  • −1≤Ai≤106-1 \le A_i \le 10^6
  • Ai≠0A_i \neq 0
  • Queries of type 11 satisfy the following constraints:
    • 1≤i≤N1 \le i \le N
    • −1≤x≤106-1 \le x \le 10^6
    • x≠0x \neq 0
  • Queries of type 22 satisfy the following constraints:
    • 1≤l≤r≤N1 \le l \le r \le N

样例 1 解释:
该输入包含 99 个查询。
下面解释前 33 个查询。

  • 初始时,A=(5,−1,3,−1,2,3,4,5)A=(5,-1,3,-1,2,3,4,5)。
  • 第 11 个查询为类型 22,所考虑的子数组为 (3,−1,2,3)(3,-1,2,3)。根据题目描述的操作,无法将这些元素全部变为相等,因此输出 No。
  • 第 22 个查询为类型 11,将 A5A_5 修改为 −1-1。修改后,A=(5,−1,3,−1,−1,3,4,5)A=(5,-1,3,-1,-1,3,4,5)。
  • 第 33 个查询为类型 22,所考虑的子数组为 (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
  • 类型 11 的查询满足以下约束:
    • 1≤i≤N1 \le i \le N
    • −1≤x≤106-1 \le x \le 10^6
    • x≠0x \neq 0
  • 类型 22 的查询满足以下约束:
    • 1≤l≤r≤N1 \le l \le r \le N

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

首页