F - Second Largest Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 525 点

問題文

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

Q 個のクエリが与えられるので、与えられた順に処理してください。各クエリは以下の 2 種類のいずれかです。

  • タイプ 1 : 1 p x の形式で与えられる。 A_p の値を x に変更する。
  • タイプ 2 : 2 l r の形式で与えられる。 (A_l, A_{l+1}, \ldots, A_r) において 2 番目に大きい値の個数を出力する。より厳密には、l \leq i \leq r を満たす整数 i であって、A_l, A_{l+1}, \ldots, A_r のうち A_i より大きい値がちょうど 1 種類であるものの個数を出力する。

制約

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • タイプ 1 のクエリにおいて、1 \leq p \leq N
  • タイプ 1 のクエリにおいて、1 \leq x \leq 10^9
  • タイプ 2 のクエリにおいて、1 \leq l \leq r \leq N
  • タイプ 2 のクエリが 1 つ以上存在する
  • 入力される値はすべて整数

入力

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

N Q
A_1 A_2 \ldots A_N
\text{query}_{1}
\vdots
\text{query}_{Q}

ただし、\text{query}_{i} は i 個目のクエリであり、以下のいずれかの形式で与えられる。

1 p x

2 l r

出力

タイプ 2 のクエリの個数を q として、q 行出力せよ。 i 行目には i 個目のタイプ 2 のクエリに対する答えを出力せよ。

入力例 1

5 4
3 3 1 4 5
2 1 3
2 5 5
1 3 3
2 2 4

出力例 1

1
0
2

はじめ、A = (3, 3, 1, 4, 5) です。

1 個目のクエリでは、(3, 3, 1) において 2 番目に大きい値は 1 であり、3, 3, 1 の中に 1 は 1 個あるので 1 を出力します。

2 個目のクエリでは、(5) において 2 番目に大きい値は存在しないので 0 を出力します。

3 個目のクエリでは、A = (3, 3, 3, 4, 5) となります。

4 個目のクエリでは、(3, 3, 4) において 2 番目に大きい値は 3 であり、3, 3, 4 の中に 3 は 2 個あるので 2 を出力します。

入力例 2

1 1
1000000000
2 1 1

出力例 2

0

入力例 3

8 9
2 4 4 3 9 1 1 2
1 5 4
2 7 7
2 2 6
1 4 4
2 2 5
2 2 7
1 1 1
1 8 1
2 1 8

出力例 3

0
1
0
2
4

Score: 525 points

Problem Statement

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

Process Q queries in the order they are given. Each query is of one of the following two types:

  • Type 1: Given in the form 1 p x. Change the value of A_p to x.
  • Type 2: Given in the form 2 l r. print the number of occurrences of the second largest value in (A_l, A_{l+1}, \ldots, A_r). More precisely, print the number of integers i satisfying l \leq i \leq r such that there is exactly one distinct value greater than A_i among A_l, A_{l+1}, \ldots, A_r.

Constraints

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • For type-1 queries, 1 \leq p \leq N.
  • For type-1 queries, 1 \leq x \leq 10^9.
  • For type-2 queries, 1 \leq l \leq r \leq N.
  • There is at least one type-2 query.
  • All input values are integers.

Input

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

N Q
A_1 A_2 \ldots A_N
\text{query}_{1}
\vdots
\text{query}_{Q}

Here, \text{query}_{i} is the i-th query and given in one of the following formats:

1 p x

2 l r

Output

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

Sample Input 1

5 4
3 3 1 4 5
2 1 3
2 5 5
1 3 3
2 2 4

Sample Output 1

1
0
2

Initially, A = (3, 3, 1, 4, 5).

For the first query, the second largest value in (3, 3, 1) is 1, which appears once in 3, 3, 1, so print 1.

For the second query, there is no second largest value in (5), so print 0.

The third query makes A = (3, 3, 3, 4, 5).

For the fourth query, the second largest value in (3, 3, 4), is 3, which appears twice in 3, 3, 4, so print 2.

Sample Input 2

1 1
1000000000
2 1 1

Sample Output 2

0

Sample Input 3

8 9
2 4 4 3 9 1 1 2
1 5 4
2 7 7
2 2 6
1 4 4
2 2 5
2 2 7
1 1 1
1 8 1
2 1 8

Sample Output 3

0
1
0
2
4