AT_abc343_f [ABC343F] Second Largest Query

[problemUrl]: https://atcoder.jp/contests/abc343/tasks/abc343_f 長さ $ 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 $ 種類であるものの個数を出力する。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \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 $ つ以上存在する - 入力される値はすべて整数 ### Sample Explanation 1 はじめ、$ 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 $ を出力します。