← 返回题目列表

AtCoder · joisc2022_k

K. 鱼2

中文机器翻译题面 查看原题

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

魚 2 (Fish 2) - 原题 PDF 第 1 页
原题PDF第1页
魚 2 (Fish 2) - 原题 PDF 第 2 页
原题PDF第2页
魚 2 (Fish 2) - 原题 PDF 第 3 页
原题PDF第3页
魚 2 (Fish 2) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 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