Persistent Range Query

2 secs 1024 MB
Tonegawac's icon Tonegawac

Persistent Range Query

問題文

NN 要素の非負整数の集合 S1:={a0,a1...aN2,aN1}S_{-1}:= \{a_0, a_1 ... a_{N-2}, a_{N-1} \} が与えられます.

以下の 33 種類のクエリを QQ 回処理してください. ii 個目のクエリ(0i<Q)(0 \leq i \lt Q)は以下の形式で与えられます.

  • 00 tit_i xix_i :: StiS_{t_i}xix_i を追加した集合を SiS_i とする. StiS_{t_i}xix_i を含む場合 Si:=StiS_i := S_{t_i} とする
  • 11 tit_i xix_i :: StiS_{t_i} から xix_i を削除した集合を SiS_i とする. StiS_{t_i}xix_i を含まない場合 Si:=StiS_i := S_{t_i} とする
  • 22 tit_i lil_i rir_i :: StiS_{t_i}lil_i 以上 rir_i 未満の要素の数を答える

注: 基本的に添字が 00 から始まります

制約

  • 1N,Q1051 \leq N, Q \leq 10^5
  • 0ai1090 \leq a_i \leq 10^9
  • a0,a1...aN2,aN1a_0, a_1 ... a_{N-2}, a_{N-1} は相異なる
  • 1ti<i-1 \leq t_i \lt i
  • 0xi,li,ri11090 \leq x_i, l_i, r_i - 1 \leq 10^9

入力

入力はすべて整数である。

N Q
a_0 a_1 ....     a_{N-2} a_{N-1}
query 0
query 1
.
.
.
query Q-1

出力

タイプ2のクエリに対する答えを1行ずつ出力してください.

サンプル

入力1
10 10
7 4 3 10 6 8 9 2 1 11
0 -1 16
2 0 17 19
2 -1 9 18
0 -1 8
1 0 3
2 0 1 8
2 -1 15 18
2 -1 0 18
2 3 1 16
0 3 20
出力1
0
3
6
0
10
10
入力2
10 10
1 13 5 17 4 18 9 8 11 12
0 -1 15
1 -1 2
2 0 3 5
0 1 8
0 -1 1
1 -1 17
2 3 4 13
1 0 9
1 7 18
0 7 6
出力2
1
6

Submit


Go (1.21)