F. Heroes of Making Magic III

我漫步在阳光下，耶-啊！这感觉真好！对于我们的魔法英雄们来说，这当然感觉很棒，他们正悠闲地走在一条单向道路上，与史莱姆战斗。史莱姆是虚弱无力的生物，除了被打败之外几乎一无是处。然而，英雄们却乐此不疲地与它们战斗，纯粹出于乐趣。 我们的英雄伊格纳修斯非常喜爱史莱姆。他正在观察一排史莱姆，这些史莱姆被表示为一个长度为 #cf_span[n] 的零索引整数数组 #cf_span[a]，其中 #cf_span[ai] 表示第 #cf_span[i] 个位置上的史莱姆数量。有时，史莱姆会凭空出现。当英雄们与史莱姆战斗时，他们会选择一段路径，从一端开始，到另一端结束，期间绝不离开该段。他们每次只能从当前位置向左或向右移动一格，移动时会击败移动到的格子上的一个史莱姆，因此该格子的史莱姆数量减少一。在英雄们刚开始位于段的某一端时，这一规则同样适用。 他们的目标是清空该段内所有的史莱姆，但绝不能移动到任何空格（即没有史莱姆的格子），否则他们会感到无聊。由于伊格纳修斯热爱史莱姆，他并不真的想消灭它们，因此在本题的所有事件中，没有任何史莱姆受到伤害。但他希望你能告诉他：如果他想的话，是否能以这种方式清空某个指定的史莱姆段。 你将收到 #cf_span[q] 个查询，分为两种类型： 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200 000])，表示数组 #cf_span[a] 的长度。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 5 000])，表示每个格子初始的史莱姆数量。第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 300 000])，表示查询数量。接下来的 #cf_span[q] 行每行包含一个查询。每个查询由整数 #cf_span[a], #cf_span[b] 和可能的 #cf_span[k] 给出 (#cf_span[0 ≤ a ≤ b < n], #cf_span[0 ≤ k ≤ 5 000])。 对于每个第二类查询，如果可以清空该段，则输出 #cf_span[1]，否则输出 #cf_span[0]。 对于第一个查询，可以轻易验证：在不清理所有史莱姆的情况下，无法从第一个格子走到最后一个格子。但在将第二个位置的史莱姆数量增加 1 后，我们就可以清空该段，例如通过以下移动方式： . ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200 000])，表示数组 #cf_span[a] 的长度。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 5 000])，表示每个格子初始的史莱姆数量。第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 300 000])，表示查询数量。接下来的 #cf_span[q] 行每行包含一个查询。每个查询由整数 #cf_span[a], #cf_span[b] 和可能的 #cf_span[k] 给出 (#cf_span[0 ≤ a ≤ b < n], #cf_span[0 ≤ k ≤ 5 000])。 ## Output 对于每个第二类查询，如果可以清空该段，则输出 #cf_span[1]，否则输出 #cf_span[0]。 [samples] ## Note 对于第一个查询，可以轻易验证：在不清理所有史莱姆的情况下，无法从第一个格子走到最后一个格子。但在将第二个位置的史莱姆数量增加 1 后，我们就可以清空该段，例如通过以下移动方式： .

Let $ a = [a_0, a_1, \dots, a_{n-1}] $ be a zero-indexed array of non-negative integers, where $ a_i $ denotes the number of imps at position $ i $. A query is of one of two types: 1. **Update**: Given $ a, k $, set $ a_a \leftarrow a_a + k $. 2. **Query**: Given $ a, b $, determine whether it is possible to traverse the segment $ [a, b] $ (inclusive) starting at one endpoint and ending at the other, moving only left or right by one cell at a time, such that: - Every cell in $ [a, b] $ is visited exactly once per imp it contains (i.e., each imp is defeated exactly once), - No move is made to a cell with zero imps at the time of the move, - The path starts at either $ a $ or $ b $, and ends at the other. --- **Formal Condition for Query Type 2 (on segment $ [l, r] $):** Let $ S = \sum_{i=l}^{r} a_i $ be the total number of imps in the segment. It is possible to clear the segment if and only if: 1. $ S > 0 $, and 2. The segment is **connected** in the sense that **no interior zero** blocks the path — i.e., for every $ i \in (l, r) $, if $ a_i = 0 $, then the segment cannot be traversed unless the zero is at an endpoint. But more precisely: **the path must be able to proceed without stepping on a zero before it is cleared**. Since we can only move to adjacent cells and must defeat one imp per move, the traversal is equivalent to an Eulerian path on a path graph where each node $ i $ has weight $ a_i $, and we must traverse $ a_i $ times through node $ i $ (except the endpoints, which are entered/exited one fewer time). This reduces to a known problem: **Can we traverse the segment $ [l, r] $ starting at one end and ending at the other, visiting each cell $ i $ exactly $ a_i $ times, moving only between adjacent cells, without stepping on a cell with zero imps at the time of visit?** This is possible **if and only if**: - The total number of imps $ S = \sum_{i=l}^{r} a_i $ is positive. - For every prefix $ [l, j] $ where $ l \leq j < r $, the cumulative sum $ \sum_{i=l}^{j} a_i > 0 $ (so we never get stuck before reaching the end), - And similarly, for every suffix $ [j, r] $ where $ l < j \leq r $, the cumulative sum $ \sum_{i=j}^{r} a_i > 0 $. But since we can choose to start at either end, we only require that **there exists a direction** (left-to-right or right-to-left) such that all **prefix sums** (in that direction) remain strictly positive until the final step. Thus, the condition becomes: > There exists a direction $ d \in \{ \text{left-to-right}, \text{right-to-left} \} $ such that, when traversing in direction $ d $, the cumulative sum of imps from the start up to (but not including) the current position is always **positive** at every step before the final imp is defeated. Equivalently, define: - $ \text{prefix}_\text{LR}(j) = \sum_{i=l}^{j} a_i $ for $ j \in [l, r-1] $ - $ \text{prefix}_\text{RL}(j) = \sum_{i=j}^{r} a_i $ for $ j \in [l+1, r] $ Then the segment $ [l, r] $ is clearable if and only if: $$ \left( \min_{j=l}^{r-1} \sum_{i=l}^{j} a_i > 0 \right) \quad \lor \quad \left( \min_{j=l+1}^{r} \sum_{i=j}^{r} a_i > 0 \right) $$ Note: We do **not** require the final cumulative sum to be positive — it becomes zero at the last step, which is allowed (we defeat the last imp and stop). But we **do** require that **before** defeating the last imp, we never step on a zero. So for a left-to-right traversal, we require that for every $ j \in [l, r-1] $, the sum $ \sum_{i=l}^{j} a_i \geq 1 $ (since we must have at least one imp remaining to step forward). Similarly for right-to-left. Thus, the condition is: $$ \boxed{ \min_{j=l}^{r-1} \sum_{i=l}^{j} a_i \geq 1 \quad \lor \quad \min_{j=l+1}^{r} \sum_{i=j}^{r} a_i \geq 1 } $$ **Note**: If $ l = r $, then the segment has one cell. It is clearable if and only if $ a_l > 0 $. --- **Summary of Formal Problem Statement:** Given: - Array $ a \in \mathbb{Z}_{\geq 0}^n $ - $ q $ queries of two types: 1. $ \texttt{update}(a, k) $: $ a_a \leftarrow a_a + k $ 2. $ \texttt{query}(l, r) $: Output $ 1 $ if $ \exists \text{ direction } d \in \{\text{LR}, \text{RL}\} $ such that: - If $ d = \text{LR} $: $ \min_{j=l}^{r-1} \sum_{i=l}^{j} a_i \geq 1 $ - If $ d = \text{RL} $: $ \min_{j=l+1}^{r} \sum_{i=j}^{r} a_i \geq 1 $ - (And if $ l = r $, then output $ 1 $ iff $ a_l > 0 $) Otherwise output $ 0 $. This is the formal mathematical statement.