以下是来自日本的官方日本新闻原版PDF,已完整保存并按原样染色。




可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 2 – Employment
雇用計画(Employment)
あなたはJust Odd Inventions 社を知っているだろうか?この会社の業務は「ただ奇妙な発明(just odd
inventions)」をすることである.ここでは略してJOI 社と呼ぶ.
JOI 社は事業を拡大するため,新たに社員を雇用することになった.
社員の候補者がN 人いる.候補者にはそれぞれ1 からN までの番号が付けられており,それぞれの候補
者には評価値と呼ばれる一つの整数が定められている.
今回の雇用では,評価値がある値以上の候補者を全員採用する.新たに採用された社員をいくつかのグ
ループに分ける.新たに採用された社員のグループを,次の条件をみたすように作る.
• 候補者a と候補者b (a < b) が両方とも採用されたとき,これらの社員が同じグループに入るのは,候
補者c (a ≦c ≦b) が全員採用された場合であり,かつそのときに限る.
JOI 社の人事担当であるあなたは,クエリを合計M 個順に処理することで,今回の雇用において作られ
るグループの個数を見積もることになった.j 番目のクエリは,以下の2 種類のうちのいずれかである.
• 評価値がBj 以上の候補者を全員採用する場合に作られるグループの個数を求める.この種類のクエ
リを解答クエリと呼ぶ.
• 候補者C j の評価値をDj に更新する.この種類のクエリを更新クエリと呼ぶ.
課題
M 個のクエリについての情報が与えられたとき,それぞれの解答クエリに対するグループの個数を求め
るプログラムを作成せよ.
入力
標準入力から以下のデータを読み込め.
• 1 行目には,整数N, M が空白を区切りとして書かれている.これは,社員の候補者がN 人いて,あ
なたがM 個のクエリを処理することを表す.
• 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Ai が書かれている.これは,クエリを処理する以
前は,候補者i の評価値がAi であることを表す.
• 続くM 行のうちのj 行目(1 ≦j ≦M) には,2 個または3 個の整数が空白を区切りとして書かれて
いる.1 個目の整数をT j とすると,この行の内容は以下のいずれかである.
1. T j = 1 のとき.この行には整数T j, Bj が空白を区切りとして書かれている.これは,j 番目のク
エリが,評価値がBj 以上の候補者を全員採用する場合に作られるグループの個数を求める解答
クエリであることを表す.
雇用計画– 1 / 4
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 2 – Employment
2. T j = 2 のとき.この行には整数T j,C j, Dj が空白を区切りとして書かれている.これは,j 番目
のクエリが,候補者C j の評価値をD j に更新する更新クエリであることを表す.
出力
標準出力に,それぞれの解答クエリに対するグループの個数を順に1 行ずつ出力せよ,
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦200 000.
• 1 ≦M ≦200 000.
• 1 ≦Ai ≦1 000 000 000 (1 ≦i ≦N).
• 1 ≦T j ≦2 (1 ≦j ≦M).
• 1 ≦Bj ≦1 000 000 000 (1 ≦j ≦M).
• 1 ≦C j ≦N (1 ≦j ≦M).
• 1 ≦Dj ≦1 000 000 000 (1 ≦j ≦M).
• T j = 1 となるj (1 ≦j ≦M) は少なくとも一つ存在する.
小課題
小課題1 [10 点]
以下の条件を満たす.
• N ≦2 000.
• M ≦2 000.
小課題2 [30 点]
• T j = 1 (1 ≦j ≦M) を満たす.
小課題3 [60 点]
追加の制限はない.
雇用計画– 2 / 4
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 2 – Employment
入出力例
入力例1 出力例1
5 4 2
8 1
6 2
3
5
4
1 5
2 4 1
1 5
1 3
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 を出力する.
雇用計画– 3 / 4
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 2 – Employment
入力例2 出力例2
7 5 0
13 1
19 3
1 3
15 2
13
1
19
1 20
1 1
1 6
1 11
1 17
入力例2 は小課題2 の制限を満たす.
入力例3 出力例3
10 5 2
8 1
10 0
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16
雇用計画– 4 / 4