問題一覧 > 通常問題

No.3164 [Chery 7th Tune B] La vie en rose

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 71
作問者 : 👑 Kazun / テスター : Taka 👑 p-adic
お気に入りにしたユーザー ProblemId : 10187 / 自分の提出
問題文最終更新日: 2025-05-20 00:16:39
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 468 Desire for Approval ~Ash blown by the draft leads to the door to a new beginning~ (順位表) の他の問題:

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.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。