004 - 雇用計画 (Employment)

時間制限 5 秒 / メモリ制限 512 MB / 得点 100 / x 1 /


TLE
5sec
MLE
512MB
得点
100

問題

あなたは Just Odd Inventions 社を知っているだろうか?この会社の業務は「ただ奇妙な発明(just odd inventions)」をすることである.ここでは略して JOI 社と呼ぶ.

JOI 社は事業を拡大するため,新たに社員を雇用することになった.

社員の候補者が N 人いる.候補者にはそれぞれ 1 から N までの番号が付けられており,それぞれの候補者には 評価値 と呼ばれる一つの整数が定められている.

今回の雇用では,評価値がある値以上の候補者を全員採用する.新たに採用された社員をいくつかのグループに分ける.新たに採用された社員のグループを,次の条件をみたすように作る.

  • 候補者 a と候補者 b (a < b) が両方とも採用されたとき,これらの社員が同じグループに入るのは,候補者 c (acb) が全員採用された場合であり,かつそのときに限る.

JOI 社の人事担当であるあなたは,クエリを合計 M 個順に処理することで,今回の雇用において作られるグループの個数を見積もることになった.j 番目のクエリは,以下の 2 種類のうちのいずれかである.

  • 評価値が Bj 以上の候補者を全員採用する場合に作られるグループの個数を求める.この種類のクエリを 解答クエリ と呼ぶ.
  • 候補者 Cj の評価値を Dj に更新する.この種類のクエリを 更新クエリ と呼ぶ.

課題

M 個のクエリについての情報が与えられたとき,それぞれの解答クエリに対するグループの個数を求めるプログラムを作成せよ.

入力

標準入力から以下のデータを読み込め.

  • 1 行目には,整数 N, M が空白を区切りとして書かれている.これは,社員の候補者が N 人いて,あなたが M 個のクエリを処理することを表す.
  • 続く N 行のうちの i 行目 (1 ≤ iN) には,整数 Ai が書かれている.これは,クエリを処理する以前は,候補者 i の評価値が Ai であることを表す.
  • 続く M 行のうちの j 行目 (1 ≤ jM) には,2 個または 3 個の整数が空白を区切りとして書かれている.1 個目の整数を Tj とすると,この行の内容は以下のいずれかである.
    1. Tj = 1 のとき.この行には整数 Tj, Bj が空白を区切りとして書かれている.これは,j 番目のクエリが,評価値が Bj 以上の候補者を全員採用する場合に作られるグループの個数を求める解答クエリであることを表す.
    2. Tj = 2 のとき.この行には整数 Tj, Cj, Dj が空白を区切りとして書かれている.これは,j 番目のクエリが,候補者 Cj の評価値を Dj に更新する更新クエリであることを表す.

出力

標準出力に,それぞれの解答クエリに対するグループの個数を順に 1 行ずつ出力せよ,

制限

すべての入力データは以下の条件を満たす.

  • 1 ≤ N ≤ 200 000.
  • 1 ≤ M ≤ 200 000.
  • 1 ≤ Ai ≤ 1 000 000 000 (1 ≤ iN).
  • 1 ≤ Tj ≤ 2 (1 ≤ jM).
  • 1 ≤ Bj ≤ 1 000 000 000 (1 ≤ jM).
  • 1 ≤ CjN (1 ≤ jM).
  • 1 ≤ Dj ≤ 1 000 000 000 (1 ≤ jM).
  • Tj = 1 となる j (1 ≤ jM) は少なくとも一つ存在する.

小課題

小課題 1 [10 点]

以下の条件を満たす.

  • N ≤ 2 000.
  • M ≤ 2 000.

小課題 2 [30 点]

  • Tj = 1 (1 ≤ jM) を満たす.

小課題 3 [60 点]

追加の制限はない.

入出力例

入力例 1

5 4
8
6
3
5
4
1 5
2 4 1
1 5
1 3

出力例 1

2
1
2
  1. 1 番目のクエリは解答クエリである.評価値が 5 以上である候補者 1, 候補者 2, 候補者 4 を採用した場合,候補者 1 と候補者 2 からなるグループと,候補者 4 からなるグループの 2 個のグループが作られるので,2 を出力する.
  2. 2 番目のクエリは更新クエリである.候補者 4 の評価値を 1 に更新する.
  3. 3 番目のクエリは解答クエリである.評価値が 5 以上である候補者 1 と候補者 2 を採用した場合,候補者 1 と候補者 2 からなる 1 個のグループが作られるので,1 を出力する.
  4. 4 番目のクエリは解答クエリである.評価値が 3 以上である候補者 1, 候補者 2, 候補者 3, 候補者 5 を採用した場合,候補者 1, 候補者 2, 候補者 3 からなるグループと,候補者 5 からなるグループの 2 個のグループが作られるので,2 を出力する.

入力例 2

7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17

出力例 2

0
1
3
3
2

入力例 2 は小課題 2 の制限を満たす.

入力例 3

10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16

出力例 3

2
1
0