以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。




可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Fish 2
魚2 (Fish 2)
JOI 君はN 匹の魚を飼育しており,それぞれの魚に1 からN までの番号を付けている.魚i (1 ≦i ≦N)
の大きさはAi である.
魚の飼育において,2 匹の魚が隣接している時,十分に時間が経過すると片方がもう一方を食べてしまう
ことに注意する必要がある.ここで,2 匹の魚が隣接するとは,その間に他の魚が存在しないことを意味す
る.具体的には,魚x の大きさが魚y の大きさ以上であり,かつ魚x と魚y が隣接している時,魚x が魚
y を食べてしまい,魚x の大きさは魚x と魚y の大きさの和になる.魚x と魚y の大きさが等しい場合は,
どちらが相手を食べることもあり得る.
JOI 君はこれからQ 日間,魚を飼育しつつ,暇つぶしに思考実験をすることにした.j 日目(1 ≦j ≦Q)
には,以下のいずれかの行動をする.
• タイプ1 : 魚Xj に特殊な餌を与えることで,大きさをYj にする.
• タイプ2 : Lj 以上Rj 以下の番号の魚のみを考え,以下の思考実験を行う:
水槽を用意し,左から順に魚L j, Lj + 1, . . . , Rj を入れる.この時,上記の魚の性質より,最終的に水
槽の中には1 匹の魚が残るが,その魚の番号は,食べる魚の選択と食べるタイミングによって定ま
る.その番号としてあり得るものは何個あるかを求める.ここで,思考実験の途中で2 匹の魚の順序
が入れ替わることはなく,また2 匹の魚が同一の魚を同時に食べることもない.
JOI 君が飼育する魚の情報とJOI 君の計画の情報が与えられたとき,JOI 君の思考が正しいかどうかを判
定するため,それぞれのタイプ2 の行動で求める,最後の1 匹の魚の番号としてあり得るものの個数を計算
するプログラムを作成せよ.なお,上記はあくまで思考実験であり,どの魚も実際には食べられることはな
いため,安心してほしい.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N
A1 A2 · · · AN
Q
(Query 1)
(Query 2)
...
(Query Q)
魚2– 1 / 4
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Fish 2
各(Query j) (1 ≦j ≦Q) にはいくつかの整数が空白区切りで書かれている.そのうち1 個目の整数をT j
とすると,この行の内容は以下のいずれかである.
• T j = 1 のとき,この行には続いて2 個の整数Xj, Yj がこの順に書かれている.これはJOI 君がj 日
目に取る行動がタイプ1 であり,魚X j の大きさをYj にすることを表す.
• T j = 2 のとき,この行には続いて2 個の整数Lj, R j がこの順に書かれている.これはJOI 君がj 日目
に取る行動がタイプ2 であり,Lj 以上Rj 以下の番号の魚のみを考え,思考実験を行うことを表す.
出力
タイプ2 の行動,すなわち,T j = 2 となるj (1 ≦j ≦Q) それぞれに対して,最後の1 匹の魚の番号とし
てあり得るものの個数を標準出力に順に改行区切りで出力せよ.
制約
• 1 ≦N ≦100 000.
• 1 ≦Q ≦100 000.
• 1 ≦Ai ≦1 000 000 000 (= 109) (1 ≦i ≦N).
• T j は1, 2 のいずれかである(1 ≦j ≦Q).
• 1 ≦X j ≦N (1 ≦j ≦Q).
• 1 ≦Y j ≦1 000 000 000 (= 109) (1 ≦j ≦Q).
• 1 ≦L j ≦R j ≦N (1 ≦j ≦Q).
小課題
1. (5 点) N ≦500,Q ≦500.
2. (8 点) Q = 1,T j = 2,Lj = 1,Rj = N (1 ≦j ≦Q).
3. (12 点) Q ≦1 000.
4. (23 点) T j = 2 (1 ≦j ≦Q).
5. (35 点) T j = 2 のときLj = 1,R j = N (1 ≦j ≦Q).
6. (17 点) 追加の制約はない.
魚2– 2 / 4
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Fish 2
入出力例
入力例1 出力例1
5 5
6 4 2 2 6 2
6 2
2 1 5 3
2 1 3 1
1 3 1
2 2 5
2 1 5
2 2 4
JOI 君の6 日間の行動は以下のようになる.
• 1 日目には,魚1, 2, 3, 4, 5 に対して思考実験を行う.
• 2 日目には,魚1, 2, 3 に対して思考実験を行う.
• 3 日目には,魚3 に特殊な餌を与えることで,大きさを1 にする.
• 4 日目には,魚2, 3, 4, 5 に対して思考実験を行う.
• 5 日目には,魚1, 2, 3, 4, 5 に対して思考実験を行う.
• 6 日目には,魚2, 3, 4 に対して思考実験を行う.
特に,1 日目の思考実験の詳細は以下の通りである.
• 水槽にいる魚の大きさは左から順番に6, 4, 2, 2, 6 である.
• 例えば,魚2 が最後の1 匹になるような手順として,以下のようなものが考えられる.(以下の数列
は水槽にいる魚の大きさを左から順に記載したものであり,太字は魚2 の大きさを示す.)
[6, 4, 2, 2, 6](最初の状態)→[6, 4, 4, 6](魚4 が魚3 を食べる)→[6, 8, 6](魚2 が魚4 を食べる)→
[14, 6](魚2 が魚1 を食べる)→[20](魚2 が魚5 を食べる)
• 同様に考えることで,最後の1 匹の魚の番号としてあり得るものは1, 2, 3, 4, 5 であり,個数は5 個で
あることが分かる.
この入力例は小課題1, 3, 6 の制約を満たす.
魚2– 3 / 4
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Fish 2
入力例2 出力例2
13 7
10 4 2 5 20 5 4 8 20 10 3 3 7
1
2 1 13
この入力例はすべての小課題の制約を満たす.
入力例3 出力例3
12 12
32 32 4 1 1 1 1 4 4 16 32 128 1
7 1
2 1 12 2
2 2 6 6
2 8 10 2
2 1 9 1
2 3 8
2 5 9
2 2 12
この入力例は小課題1, 3, 4, 6 の制約を満たす.
入力例4 出力例4
10 4
2 3 5 10 1 3 4 9 5 2 6
8 1
2 1 10 6
1 10 5
2 1 10
1 4 1000000000
2 1 10
1 8 20
1 4 8
2 1 10
この入力例は小課題1, 3, 5, 6 の制約を満たす.
魚2– 4 / 4