F - Make them monochrome 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N) があります。
以下の Q 個のクエリを処理してください。

タイプ 1 :

1 i x

A_i を x に変更する。

タイプ 2 : 

2 l r

A_l,A_{l+1},\dots,A_r に含まれる -1 をそれぞれ任意の正整数に置き換えることができるとき、 A_l,A_{l+1},\dots,A_r を全て等しくできるなら Yes 、そうでないなら No と出力する。

制約

  • 入力は全て整数
  • 1 \le N,Q \le 3 \times 10^5
  • -1 \le A_i \le 10^6
  • A_i \neq 0
  • タイプ 1 のクエリは以下の制約を満たす
    • 1 \le i \le N
    • -1 \le x \le 10^6
    • x \neq 0
  • タイプ 2 のクエリは以下の制約を満たす
    • 1 \le l \le r \le N

入力

入力は以下の形式で標準入力から与えられる。 ただし、 {\rm Query}_i は i 個目のクエリを表す。

N Q
A_1 A_2 \dots A_N
{\rm Query}_1
{\rm Query}_2
\vdots
{\rm Query}_Q

出力

タイプ 2 のクエリが与えられるごとに、そのクエリの答えを 1 行に出力せよ。

入力例 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

この入力には 9 個のクエリが含まれます。
以下では、最初 3 個のクエリについて説明します。

  • 最初、 A=(5,-1,3,-1,2,3,4,5) です。
  • 1 個目のクエリはタイプ 2 で、問われている部分列は (3,-1,2,3) です。これらを問題文中の操作で全て等しくすることはできないため、 No と出力します。
  • 2 個目のクエリはタイプ 1 で、 A_5 を -1 に変更します。その結果、 A=(5,-1,3,-1,-1,3,4,5) となります。
  • 3 個目のクエリはタイプ 2 で、問われている部分列は (3,-1,-1,3) です。これらを問題文中の操作で全て等しくすることができるため、 Yes と出力します。

Score : 500 points

Problem Statement

There is an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
Process the following Q queries.

Type 1 :

1 i x

Change A_i to x.

Type 2 :

2 l r

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

Constraints

  • All input values are integers.
  • 1 \le N,Q \le 3 \times 10^5
  • -1 \le A_i \le 10^6
  • A_i \neq 0
  • Queries of type 1 satisfy the following constraints:
    • 1 \le i \le N
    • -1 \le x \le 10^6
    • x \neq 0
  • Queries of type 2 satisfy the following constraints:
    • 1 \le l \le r \le N

Input

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

N Q
A_1 A_2 \dots A_N
{\rm Query}_1
{\rm Query}_2
\vdots
{\rm Query}_Q

Output

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

Sample Input 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

Sample Output 1

No
Yes
Yes
No
Yes

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 A_5 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.