P9530 [JOIST 2022] Fish 2 / Fish 2

JOISC2022 D4T2

JOI has $N$ fish, numbered $1,2,\dots,N$. The size of fish $i$ $(1 \le i \le N)$ is $A_i$. When raising fish, we need to pay attention to the following fact: if two fish are close to each other, then as time passes, one of them may eat the other. Two fish are close to each other if and only if there is no fish between them. More specifically, if fish $x$ has size not less than fish $y$, and fish $x,y$ are close to each other, then $x$ can eat $y$, and the size of $x$ becomes the sum of the original sizes of $x$ and $y$. If $x$ and $y$ have the same size, then either $x$ eats $y$ or $y$ eats $x$ may happen. JOI will raise fish for $Q$ days. To pass the time, he will do the following thought experiment. On day $j$ $(1 \le j \le Q)$, JOI will perform one of the following actions: - Type 1: JOI feeds fish $X_j$ some special food. This changes the size of fish $X_j$ to $Y_j$. - Type 2: JOI takes out the fish with indices in the interval $[L_j,R_j]$ and performs the following experiment: JOI puts fish $L_j,L_j+1,\dots,R_j$ into a fish tank from left to right in order. Due to the property described above, in the end only one fish will survive. The index of the surviving fish depends on which fish eat which fish at which times. JOI wants to know how many fish could possibly become the final survivor. During the experiment, fish indices do not change, and it is not allowed that two fish eat the same fish at the same time. Write a program that, given JOI's fish and the experiment information, computes the answer for each Type 2 action, so that JOI can prove or disprove his idea. Note that this is only a thought experiment; no fish are actually eaten.

The first line contains a positive integer $N$, representing the number of fish. The second line contains $N$ positive integers $A_1,A_2,\dots,A_N$, representing the size of each fish. The third line contains a positive integer $Q$, representing the number of days of raising fish. The next $Q$ lines describe the operations. On line $j$ $(1 \le j \le Q)$, there are several space-separated integers, and the first integer is $T_j$, representing the operation type. - If $T_j=1$, then the line also contains two positive integers $X_j,Y_j$, meaning that on day $j$ JOI performed a Type 1 action. The size of fish $X_j$ becomes $Y_j$. - If $T_j=2$, then the line also contains two positive integers $L_j,R_j$, meaning that on day $j$ JOI performed a Type 2 action. JOI performs an experiment on the fish with indices in $[L_j,R_j]$.

For each Type 2 action (that is, for each $j$ $(1 \le j \le Q)$ with $T_j=2$), output one line with one integer, representing how many fish could possibly become the final survivor.

**Sample Explanation #1** Over $6$ days, JOI performed the following actions: - Day 1: He performed an experiment on fish $1,2,3,4,5$. - Day 2: He performed an experiment on fish $1,2,3$. - Day 3: He fed fish $3$ special food, changing its size to $1$. - Day 4: He performed an experiment on fish $2,3,4,5$. - Day 5: He performed an experiment on fish $1,2,3,4,5$. - Day 6: He performed an experiment on fish $2,3,4$. The result of the experiment on Day 1 is as follows: - The fish sizes in the tank in order are $[6,4,2,2,6]$. - For example, through the following process, fish $2$ can become the final survivor (where the bold number is the size of fish $2$). $[6,\textbf 4,2,2,6]$ (initial state) $\longrightarrow$ $[6,\textbf 4,4,6]$ (fish $4$ eats fish $3$) $\longrightarrow$ $[6,\textbf 8,6]$ (fish $2$ eats fish $4$) $\longrightarrow$ $[\textbf{14},6]$ (fish $2$ eats fish $1$) $\longrightarrow$ $[\textbf{20}]$ (fish $2$ eats fish $5$). - Similarly, fish $1,2,3,4,5$ can all become the final survivor. Therefore, the answer is $5$. This sample satisfies the constraints of subtasks $1,3,6$. **Sample Explanation #2** This sample satisfies the constraints of all subtasks. **Sample Explanation #3** This sample satisfies the constraints of subtasks $1,3,4,6$. **Sample Explanation #4** This sample satisfies the constraints of subtasks $1,3,5,6$. **Constraints** For all testdata, it holds that: - $1 \le N,Q \le 100\,000$. - $1 \le A_i \le 10^9$ $(1\le i\le N)$. - $T_j \in \{1,2\}$. - $1 \le X_j \le N$ $(1\le j\le Q)$. - $1 \le Y_j \le 10^9$。 - $1 \le L_j \le R_j \le N$ $(1 \le j \le Q)$. The additional constraints and scores for subtasks are shown in the table below: |Subtask ID|Additional Constraints|Score| |:-:|:-:|:-:| |$1$|$N \le 500$, $Q \le 500$|$5$| |$2$|$Q=1$, $T_j=2$, $L_j=1$, $R_j=N$ $(1 \le j \le Q)$|$8$| |$3$|$Q\le 1\,000$|$12$| |$4$|$T_j=2$ $(1 \le j\le Q)$|$23$| |$5$|For each $j$ $(1\le j\le Q)$ with $T_j=2$, it holds that $L_j=1$, $R_j=N$|$35$| |$6$|No additional constraints|$17$| Translated by ChatGPT 5