No.3164 [Chery 7th Tune B] La vie en rose
Problem Visual
▶ Open to reveal the problem visual
Problem Statement
There is a long, horizontally extending flower bed. This flower bed is divided into $N$ sections in a row. The $i$-th section from the left is called section $i$.
In section $i~(1 \leq i \leq N)$, $A_i$ roses are blooming. A section is called a "rose-blooming section" if and only if at least $1$ rose is blooming in it.
For $2$ distinct sections, section $i$ and section $j$, section $i$ and section $j$ are adjacent if and only if $\lvert i - j \rvert = 1$.
Answer $Q$ queries $q~(1 \leq q \leq Q)$ given in the following form.
- Query $q$: Suppose that the number of roses blooming in section $X_q$ has increased to $B_q$. Find the total number of roses blooming in the sections reachable from section $X_q$ by moving between adjacent rose-blooming sections $0$ or more times.
That is, solve the following problem.Let $C_j$ be the number of roses blooming in section $j$ after the number of blooming roses has changed. Find the sum of $C_i$ over all integers $i$ between $1$ and $N$, inclusive, that satisfy the following condition.
- There exists an integer sequence $(p_1, p_2, \dots, p_n)$ of length at least $1$ that satisfies all of the following.
- For $k = 1, 2, \dots, n$, $1 \leq p_k \leq N$.
- $p_1=X_q, p_n=i$.
- For $k = 1, 2, \dots, (n-1)$, section $p_k$ and section $p_{k+1}$ are adjacent. That is, $\lvert p_k - p_{k+1} \rvert = 1$.
- For $k = 1, 2, \dots, n$, section $p_k$ is a rose-blooming section. That is, $C_{p_k} \geq 1$.
Note that, by the constraints, section $X_q$ is always a rose-blooming section.
- There exists an integer sequence $(p_1, p_2, \dots, p_n)$ of length at least $1$ that satisfies all of the following.
The $Q$ queries are independent. That is, a change in the number of blooming roses in one query does not affect any other query.
Constraints
- $1 \leq N \leq 3 \times 10^5$.
- $0 \leq A_i \lt 10^9 \quad (1 \leq i \leq N)$.
- $1 \leq Q \leq 3 \times 10^5$.
- $1 \leq X_q \leq N \quad (1 \leq q \leq Q)$.
- $A_{X_q} < B_q \leq 10^9 \quad (1 \leq q \leq Q)$.
- All input values are integers.
Input
$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $Q$ $X_1$ $B_1$ $X_2$ $B_2$ $\vdots$ $X_Q$ $B_Q$
Output
The output consists of $Q$ lines. On line $q~(1 \leq q \leq Q)$, print the answer to query $q$ as an integer.
Since the input and output may be large, it is recommended to use fast input and output methods.
Sample
Sample 1
Input
10 1 0 3 4 5 0 7 0 0 10 3 4 100 2 2 7 7777777
Output
108 15 7777777
- [Query $1$]
In this query, the number of roses blooming in section $4$ changes from $4$ to $100$.
Then, the sections reachable from section $4$ by moving between adjacent sections $0$ or more times are the $3$ sections: section $3$, section $4$, and section $5$.
The total number of roses blooming in section $3$, section $4$, and section $5$ is $3 + 100 + 5 = 108$.
- [Query $2$]
In this query, the number of roses blooming in section $2$ changes from $0$ to $2$. Here, this query is not affected by the change to the number of roses blooming in section $4$ made in query $1$. That is, note that the number is $4$, not $100$.
Then, the sections reachable from section $2$ by moving between adjacent sections $0$ or more times are the $5$ sections: section $1$, section $2$, section $3$, section $4$, and section $5$.
The total number of roses blooming in section $1$, section $2$, section $3$, section $4$, and section $5$ is $1 + 2 + 3 + 4 + 5 = 15$.
Sample 2
Input
2 0 1018 1 1 2023
Output
3041
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun