F - 連 解説 /

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

配点 : 3 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

クエリを Q 個処理してください。クエリは以下の 2 種類のいずれかです。

  • 1 i x：A_i を x に変更する。
  • 2 l r：正の整数 k であって、次の条件を満たすものの最大値を出力する。
    • ある整数 p が存在し、l \leq p \leq p+k-1 \leq r かつ A_p=A_{p+1}=\cdots=A_{p+k-1} である。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 種類目のクエリについて、1 \leq i \leq N, 0 \leq x \leq 10^9
  • 2 種類目のクエリについて、1 \leq l \leq r \leq N
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下のいずれかの形式で与えられる。

1 i x

2 l r

出力

2 種類目のクエリの個数を q として、q 行出力せよ。j 行目には、j 番目の 2 種類目のクエリに対する答えを出力せよ。

入力例 1

8 7
1 1 2 2 2 3 2 2
2 1 8
2 4 8
1 6 2
2 3 8
1 4 7
2 1 8
2 4 4

出力例 1

3
2
6
4
1

はじめの 2 つのクエリに対する答えは、それぞれ 3,2 です。

3 番目のクエリを処理した後、A=(1,1,2,2,2,2,2,2) となるため、続くクエリに対する答えは 6 です。

入力例 2

6 7
0 1000000000 1000000000 0 0 0
2 1 6
2 2 5
1 3 0
2 2 6
1 2 0
2 1 6
1 6 1000000000

出力例 2

3
2
4
6

Score: 3 points

Problem Statement

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 2 types:

  • 1 i x: Change A_i to x.
  • 2 l r: Print the largest positive integer k satisfying the following condition:
    • There exists an integer p such that l \leq p \leq p+k-1 \leq r and A_p=A_{p+1}=\cdots=A_{p+k-1}.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • For type 1 queries, 1 \leq i \leq N, 0 \leq x \leq 10^9
  • For type 2 queries, 1 \leq l \leq r \leq N
  • All numerical values in the input are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following formats:

1 i x

2 l r

Output

Let q be the number of type 2 queries. Print q lines. The j-th line should contain the answer to the j-th type 2 query.

Sample Input 1

8 7
1 1 2 2 2 3 2 2
2 1 8
2 4 8
1 6 2
2 3 8
1 4 7
2 1 8
2 4 4

Sample Output 1

3
2
6
4
1

The answers to the first 2 queries are 3,2, respectively.

After processing query 3, A=(1,1,2,2,2,2,2,2), so the answer to the next query is 6.

Sample Input 2

6 7
0 1000000000 1000000000 0 0 0
2 1 6
2 2 5
1 3 0
2 2 6
1 2 0
2 1 6
1 6 1000000000

Sample Output 2

3
2
4
6