No.2942 Sigma Music Game Level Problem
タグ : / 解いたユーザー数 79
作問者 :
kazuppa
/ テスター :
highlighter
Magentor
Story
Having failed to FC most of the test files in the previous game, kazuppa made the following resolution.
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$.
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。