問題一覧 > 通常問題

No.2311 [Cherry 5th Tune] Cherry Month

レベル : / AI推定難易度 : 2675 / 実行時間制限 : 1ケース 4.600秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 7
作問者 : 👑 Kazun / テスター : square1001
お気に入りにしたユーザー ProblemId : 5296 / 自分の提出
問題文最終更新日: 2023-05-20 01:48:37
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 389 (Until that day when "Cherry Month" is over.) (順位表) の他の問題:

Story

This is a park somewhere in Japan, famous for its cherry trees. According to legend, on the last day of the Cherry Month, the cherry trees of this park scatter their petals, and paths of those petals are formed one after another.

Today is the last day of the Cherry Month. This is the story of that miraculous $1$ day.

Problem Statement

Sakura Park has $N$ cherry trees. They are named Cherry $1$, Cherry $2$, $\cdots$, Cherry $N$.

It is now time $0$. At this moment, the $N$ cherry trees are in the following state.

  • For $i=1,2, \dots, N$, Cherry $i$ has $A_i$ petals.
  • There is no petal path between any $2$ cherry trees.

Here, for an integer $i$ between $1$ and $N$, inclusive, we say that "$k$ petals of Cherry $i$ fall" when the following happens.

  • Let $l$ be the number of petals on Cherry $i$ immediately before the falling begins. Then, the number of petals on Cherry $i$ becomes $\max(0, l-k)$.

Now, $T$ events occur on these $N$ cherry trees between time $0$ and time $T$. The $t~(1 \leq t \leq T)$-th event occurred between time $(t-0.8)$ and time $(t-0.2)$. Each event is given in one of the following formats.

  • 1 X Y: A petal path is formed between Cherry $X$ and Cherry $Y$ (it is guaranteed that there is no petal path between Cherry $X$ and Cherry $Y$ at time $(t-0.9)$).
  • 2 X K: $K$ petals of Cherry $X$ fall.
  • 3 X K: $K$ petals fall from Cherry $X$ and from every cherry tree reachable from Cherry $X$ by following $1$ petal path.
  • 4 X K: $K$ petals fall from Cherry $X$ and from every cherry tree reachable from Cherry $X$ by following some number of petal paths.

Now, regarding the $N$ cherry trees during this $1$ day, answer the following $Q$ questions $q~(1 \leq q \leq Q)$.

  • Question $q$ : Find the number of petals on Cherry $I_q$ at time $S_q$.

Note that in this problem, the $t$ in the expression "time $t$" takes continuous values. In this world, the length of $1$ day is $T$ hours, and time $T$ means time $0$ of the next day.

Constraints

  • $2 \leq N \leq 1.5 \times 10^5$.
  • $1 \leq A_i \leq 4 \times 10^{14} \quad (1 \leq i \leq N)$.
  • $1 \leq T \leq 4 \times 10^5$.
  • Constraints on events of the format 1 X Y (an event that occurred between time $(t-0.8)$ and time $(t-0.2)$)
    • $1 \leq X \leq N$.
    • $1 \leq Y \leq N$.
    • $X \neq Y$.
    • There is no petal path between Cherry $X$ and Cherry $Y$ at time $(t-0.9)$.
  • Constraints on events of the formats 2 X K, 3 X K, 4 X K
    • $1 \leq X \leq N$.
    • $1 \leq K \leq 10^9$.
  • $1 \leq Q \leq 4 \times 10^5$.
  • $T+Q \leq 4 \times 10^5$.
  • $0 \leq S_q \leq T \quad (1 \leq q \leq Q)$.
  • $1 \leq I_q \leq N \quad (1 \leq q \leq Q)$.
  • All input values are integers.

Input

The input is given from standard input in the following format.
$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$T$
$\textrm{Event}_1$
$\textrm{Event}_2$
$\vdots$
$\textrm{Event}_T$
$Q$
$\textrm{Question}_1$
$\textrm{Question}_2$
$\vdots$
$\textrm{Question}_Q$
Each event is given in one of the following $4$ formats.
$1$ $X$ $Y$
$2$ $X$ $K$
$3$ $X$ $K$
$4$ $X$ $K$
Each question $q$ is given in the following format.
$S_q$ $I_q$

Output

The output consists of $Q$ lines. On the $q~(1 \leq q \leq Q)$-th line, print the answer to question $q$ as an integer.

Do not forget the newline at the end.

Since the input and output may be large, using fast I/O methods is recommended.

Sample

Sample 1
Input
5
10 15 20 25 30
10
2 1 7
1 1 3
1 2 3
3 3 8
1 4 5
4 5 16
1 3 4
1 5 1
3 4 8
2 5 7
8
1 1
5 1
10 1
10 2
10 3
10 4
10 5
3 4
Output
3
0
0
7
4
1
0
25

The figures below show the progress through each event.

Sample 2
Input
9
2052486779 2171307413 1168176121 1168169121 1044742332 188219335 191219335 79797979 333333333
16
1 1 2
4 1 1000000000
1 2 3
2 3 10000
1 3 4
3 3 123456789
1 4 5
4 4 998244353
1 5 6
2 2 3141592
1 6 7
3 7 141421356
1 7 8
4 1 46464646
1 8 9
2 1 7777777
9
16 1
16 2
16 3
16 4
16 5
16 6
16 7
16 8
16 9
Output
3
33
333
3333
33333
333333
3333333
33333333
333333333

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