問題一覧 > 通常問題

No.2942 Sigma Music Game Level Problem

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 79
作問者 : kazuppa / テスター : highlighter Magentor hirayuu_yc
お気に入りにしたユーザー ProblemId : 11351 / 自分の提出
問題文最終更新日: 2024-10-21 20:46:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 450 (順位表) の他の問題:

Story

Having failed to FC most of the test files in the previous game, kazuppa made the following resolution.

  • Let's choose the difficulty properly!
  • So he decided to choose songs all over again.

    Problem Statement

    Initially there are $N$ songs in total, and their levels are $A_1,A_2,...\ ,A_{N}$ respectively.

    There is also a sequence $L_0,L_1,...,L_Q$ of length $Q+1$. Initially, $L_0$ is given in the input, and $L_i\ (1\leq i\leq Q)$ are initialized to $0$. In addition, $\max_{i=1}^{N}A_i\leq L_0$ holds.

    A total of $Q$ queries of the following types are given. Process them in order.

  • 1 l A new song of level $l$ is added.

    $\ \ \ \ \ $If this is the $i$-th query, it is guaranteed that $0\leq l\leq L_i$.

  • 2 l r Find the total number of songs existing at that point whose level is at least $l$ and at most $r$, and the sum of the levels of the songs satisfying that condition, and print them on one line separated by a space.

    $\ \ \ \ \ $That is, letting the number of songs of level $n$ be $F(n)$,

    $\ \ \ \ \ \displaystyle\sum_{i=l}^r F(i)$ and $\displaystyle\sum_{i=l}^r F(i)\times i$ should be printed in this order.

    $\ \ \ \ \ $If this is the $i$-th query, it is guaranteed that $0\leq l\leq r\leq L_i$.

  • 3 m If this query is the $i$-th one, set $L_i$ to $m$.

    $\ \ \ \ \ $It is guaranteed that $L_{i-1}< m\leq 200000$.

  • However, if the $i$-th query is not $3$, then $L_i=L_{i-1}$.

    If no query $2$ is given at all, print Not Found!.
  • Input

    The input is given from standard input in the following format.
    $N\ \ Q\ \ L_0$
    $A_1\ \ A_2 \ \ ...\ \ A_{N}$
    $Query_1$
    $Query_2$
    .
    .
    $Query_Q$
    
    Each query is in one of the following formats.

    $1\ \ l$
    $2\ \ l\ \ r$
    $3\ \ m$

    Constraints

    • $1\leq N,Q\leq 10^6\\ $
    • $0\leq L_0\leq 2\times 10^5\\ $
    • $0\leq A_i\leq L_0\ (1\leq i\leq N)\\ $
    • For query $1$, if this is the $i$-th query, $0\leq l\leq L_i\\ $
    • For query $2$, if this is the $i$-th query, $0\leq l\leq r\leq L_i\\ $
    • For query $3$, if this is the $i$-th query, $L_{i-1}< m\leq 10^5\times 2\\ $
    • All input values are integers

    Output

    If no query $2$ is given at all, print Not Found!. If query $2$ exists, print the answer to each query $2$ on its own line.

    Print a newline at the end.

    Sample

    Sample 1
    Input
    2 4 4
    1 3
    2 2 4
    3 6
    1 5
    2 2 5
    
    Output
    1 3
    2 8
    

    First, the levels of the songs present from the start are $1$ and $3$.

    In this problem, $L$ is $(4,4,6,6,6)$.

    Each query works as follows.

    • In the 2nd query, among songs with level at least $2$ and at most $4$, there is only one, of level $3$.
    • $\ \ \ \ $Therefore, the number of songs is $1$ and the sum of levels is $3$.

    • In the 4th query, a new song of level $5$ is added.
    • In the 5th query, the songs with level at least $2$ and at most $5$ are the two of levels $3$ and $5$.
    • $\ \ \ \ $Therefore, the number of songs is $2$ and the sum of levels is $8$.

    Sample 2
    Input
    1 1 0
    0
    1 0
    
    Output
    Not Found!
    

    There may be cases where no query $2$ is given; in such cases, print Not Found!. Also note that $L_0=0$ is possible.

    Sample 3
    Input
    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
    
    Output
    0 0
    

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