17707번 - Employment 서브태스크다국어

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

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

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

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

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

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

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

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

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

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

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

• 1 ≦ N ≦ 200 000．
• 1 ≦ M ≦ 200 000．
• 1 ≦ A_i ≦ 1 000 000 000 (1 ≦ i ≦ N)．
• 1 ≦ T_j ≦ 2 (1 ≦ j ≦ M)．
• 1 ≦ B_j ≦ 1 000 000 000 (1 ≦ j ≦ M)．
• 1 ≦ C_j ≦ N (1 ≦ j ≦ M)．
• 1 ≦ D_j ≦ 1 000 000 000 (1 ≦ j ≦ M)．
• T_j = 1 となる j (1 ≦ j ≦ M) は少なくとも一つ存在する．