問題一覧 > 通常問題

No.2942 Sigma Music Game Level Problem

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : kazuppa / テスター : highlighter Magentor hirayuu_yc
0 ProblemId : 11351 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-21 20:46:13

ストーリー

先ほどのゲームにおいてテストファイルの大半でFCできなかったkazuppa君は、次のように決意しました。

  • 難易度をちゃんと選ぼう！

    • ということで、改めて曲を選ぶことにしました。

    問題文

    初めからある曲は合計で NN 個、曲のレベルはそれぞれ A1,A2,... ,ANA_1,A_2,...\ ,A_{N} となっています。

    また、長さ Q+1Q+1 の数列 L0,L1,...,LQL_0,L_1,...,L_Q があります。はじめ L0L_0 が入力で与えられ、Li (1≤i≤Q)L_i\ (1\leq i\leq Q) は 00 で初期化されています。そして、 max⁡i=1NAi≤L0\max_{i=1}^{N}A_i\leq L_0 となっています。

    以下のクエリが合計 QQ 個与えられるので、順番に処理してください。

  • 1 l 新たにレベル ll の曲が追加される。

         \ \ \ \ \ なお、これが ii 番目のクエリの時、 0≤l≤Li0\leq l\leq L_i であることが保証されています。

  • 2 l r その時点で存在する、レベルが ll 以上 rr 以下となる曲の個数の総和とその条件を満たす曲のレベルの総和を求め、空白区切りで一行で出力してください。

         \ \ \ \ \ つまり、レベル nn の曲の数を F(n)F(n) とするとき、

         ∑i=lrF(i)\ \ \ \ \ \displaystyle\sum_{i=l}^r F(i) と ∑i=lrF(i)×i\displaystyle\sum_{i=l}^r F(i)\times i を順番に出力してください。

         \ \ \ \ \ なお、これが ii 番目のクエリの時、 0≤l≤r≤Li0\leq l\leq r\leq L_i であることが保証されています。

  • 3 m このクエリが ii 番目の時、 LiL_i を mm とする。

         \ \ \ \ \ なお、 Li−1<m≤200000L_{i-1}< m\leq 200000 であることが保証されています。

  • ただし、 ii 番目のクエリが 33 でないのなら、 Li=Li−1L_i=L_{i-1} となります。

    なお、もしクエリ 22 が一つも与えられなかった場合は、Not Found!と出力してください。

    • 入力

    入力は以下の形式で標準入力から与えられる。 
    N  Q  L0N\ \ Q\ \ L_0
A1  A2  ...  ANA_1\ \ A_2 \ \ ...\ \ A_{N}
Query1Query_1
Query2Query_2
.
.
QueryQQuery_Q
    また、各クエリについては次のうちのいずれかである。

    1  l1\ \ l
    2  l  r2\ \ l\ \ r
    3  m3\ \ m

    制約

    • 1≤N,Q≤1061\leq N,Q\leq 10^6\\
    • 0≤L0≤2×1050\leq L_0\leq 2\times 10^5\\
    • 0≤Ai≤L0 (1≤i≤N)0\leq A_i\leq L_0\ (1\leq i\leq N)\\
    • クエリ 11 において、これが ii 番目のクエリの時、 0≤l≤Li0\leq l\leq L_i\\
    • クエリ 22 において、これが ii 番目のクエリの時、 0≤l≤r≤Li0\leq l\leq r\leq L_i\\
    • クエリ 33 において、これが ii 番目のクエリの時、 Li−1<m≤105×2L_{i-1}< m\leq 10^5\times 2\\
    • 入力はすべて整数

    出力

    クエリ 22 が一つも与えられなかったらNot Found!と出力してください。 もしクエリ 22 が存在するのなら、クエリ 22 の答えをそれぞれ一行に出力してください。

    最後に改行してください。

    サンプル

    サンプル1
    入力
    2 4 4
1 3
2 2 4
3 6
1 5
2 2 5
    出力
    1 3
2 8

    まず、最初から追加されてる楽曲のレベルは 11 と 33 です。

    また、この問題における LL は、 (4,4,6,6,6)(4,4,6,6,6) となります。

    各クエリでは次のようになります。

    • 2つ目のクエリではレベルが 22 以上 44 以下の曲は 33 の一つだけです。
      •     \ \ \ \ よって、曲数は 11 、レベルの総和は 33 となります。

    • 4つ目のクエリでは 新たにレベル 55 の曲が追加されます。

    • 5つ目のクエリではレベルが 22 以上 55 以下の曲は 33 と 55 の二つです。
      •     \ \ \ \ よって、曲数は 22 、レベルの総和は 88 となります。

    サンプル2
    入力
    1 1 0
0
1 0
    出力
    Not Found!

    クエリ 22 が与えられない場合もあります、こういう時はNot Found!と出力してください。また、 L0=0L_0=0 の場合もあることに注意してください。

    サンプル3
    入力
    9 7 9
9 8 6 1 8 9 7 9 6
1 6
1 1
3 21
1 10
1 16
1 8
2 17 20
    出力
    0 0

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。