English · Original
Chinese · Translation
Formal · Original
*This is the hard version of the problem. The only difference between the two versions is the constraint on $x$. In this version, $x$ could be up to $10^5$.*
It's raining cats and corgis! ... and a whole bunch of other random animals.
As a zoology-meteorology-geology triple major, you immediately rush to the field to study the phenomenon. The field is an array of $N$ positions, where the $i^(t h)$ position has elevation $h_i$.
As you observe the unusual precipitation of animals, you notice that the animals fall from the sky and stack on top of each other. Each animal adds $1$ unit of elevation to the position where it lands. Animals continue to stack on top of each other until all valleys in the landscape are filled. Formally, a valley exists if there exist positions $i, j, k$ such that $1 <= i < j < k <= N$ and $h_i > h_j < h_k$ (Visual example provided below).
You wonder that if you increase the height of the landscape at position $i$ by $x$ units, how many animals will fill the resulting landscape.
The first line of input contains 2 space-separated integers $N, Q " "(1 <= N, Q <= 10^5) -$ the size of the landscape and the number of queries to process, respectively.
The second line of input contains $N$ integers $h_i " "(0 <= h_i <= 10^5)$ separated by spaces, representing the initial elevation at the $i^(t h)$ position in the landscape array.
Each of the following $Q$ lines contains two integers $p_i " "(1 <= p_i <= N)$ and $x_i " "(1 <= x_i <= 10^5)$, representing the position in the landscape array where the elevation will be increased by $x$ units.
*Note*: The changes made in each query should be preserved and taken into account when processing subsequent queries.
Please output $Q$ lines, where the $i^(t h)$ line contains the answer to the $i^(t h)$ query.
## Input
The first line of input contains 2 space-separated integers $N, Q " "(1 <= N, Q <= 10^5) -$ the size of the landscape and the number of queries to process, respectively.The second line of input contains $N$ integers $h_i " "(0 <= h_i <= 10^5)$ separated by spaces, representing the initial elevation at the $i^(t h)$ position in the landscape array.Each of the following $Q$ lines contains two integers $p_i " "(1 <= p_i <= N)$ and $x_i " "(1 <= x_i <= 10^5)$, representing the position in the landscape array where the elevation will be increased by $x$ units.*Note*: The changes made in each query should be preserved and taken into account when processing subsequent queries.
## Output
Please output $Q$ lines, where the $i^(t h)$ line contains the answer to the $i^(t h)$ query.
[samples]
[{"iden":"statement","content":"*这是本题的困难版本。两个版本的唯一区别在于 $x$ 的约束。在本版本中，$x$ 最多可达 $10^5$。*\n\n天上正下着猫和柯基！……还有大量其他随机动物。\n\n作为一名动物学-气象学-地质学三重专业学生，你立即冲到野外研究这一现象。该野外区域是一个包含 $N$ 个位置的数组，其中第 $i^{\\text{th}}$ 个位置的海拔为 $h_i$。\n\n当你观察这些异常的动物降水时，你注意到动物从天空落下并堆叠在彼此之上。每只动物在其落地的位置增加 $1$ 单位的海拔。动物会持续堆叠，直到景观中的所有山谷都被填满。形式上，若存在位置 $i, j, k$ 满足 $1 \\lt eq i < j < k \\lt eq N$ 且 $h_i > h_j < h_k$，则称其为一个山谷（下方提供视觉示例）。\n\n你好奇的是：若将景观中位置 $i$ 的高度增加 $x$ 个单位，将有多少只动物填满最终的景观？\n\n输入的第一行包含两个用空格分隔的整数 $N, Q$ $ (1 \\lt eq N, Q \\lt eq 10^5)$ —— 分别表示景观的大小和需要处理的查询数量。\n\n第二行输入包含 $N$ 个用空格分隔的整数 $h_i$ $ (0 \\lt eq h_i \\lt eq 10^5)$，表示景观数组中第 $i^{\\text{th}}$ 个位置的初始海拔高度。\n\n接下来的 $Q$ 行每行包含两个整数 $p_i$ $ (1 \\lt eq p_i \\lt eq N)$ 和 $x_i$ $ (1 \\lt eq x_i \\lt eq 10^5)$，表示将景观数组中位置 $p_i$ 的海拔增加 $x_i$ 个单位。\n\n*注意*：每个查询所做的更改应被保留，并在处理后续查询时一并考虑。\n\n请输出 $Q$ 行，其中第 $i^{\\text{th}}$ 行包含第 $i^{\\text{th}}$ 个查询的答案。\n"},{"iden":"input","content":"输入的第一行包含两个用空格分隔的整数 $N, Q$ $ (1 \\lt eq N, Q \\lt eq 10^5)$ —— 分别表示景观的大小和需要处理的查询数量。第二行输入包含 $N$ 个用空格分隔的整数 $h_i$ $ (0 \\lt eq h_i \\lt eq 10^5)$，表示景观数组中第 $i^{\\text{th}}$ 个位置的初始海拔高度。接下来的 $Q$ 行每行包含两个整数 $p_i$ $ (1 \\lt eq p_i \\lt eq N)$ 和 $x_i$ $ (1 \\lt eq x_i \\lt eq 10^5)$，表示将景观数组中位置 $p_i$ 的海拔增加 $x_i$ 个单位。*注意*：每个查询所做的更改应被保留，并在处理后续查询时一并考虑。"},{"iden":"output","content":"请输出 $Q$ 行，其中第 $i^{\\text{th}}$ 行包含第 $i^{\\text{th}}$ 个查询的答案。"},{"iden":"examples","content":"输入\n10 4\n2 1 4 4 5 2 3 4 5 3\n3 1\n7 1\n4 1\n5 1\n输出\n8\n7\n6\n6\n\n输入\n5 4\n0 5 0 5 0\n2 1\n4 1\n3 1\n1 1\n输出\n5\n6\n5\n5\n\n输入\n6 2\n0 0 0 0 0 0\n2 1\n4 1\n输出\n0\n1\n"},{"iden":"note","content":" "}]}
**Definitions:**
- Let $ h = [h_1, h_2, \dots, h_N] $ be the array of initial elevations.
- A **valley** is a triple of indices $ (i, j, k) $ such that $ 1 \leq i < j < k \leq N $ and $ h_i > h_j < h_k $.
- The landscape is **filled** when no valleys remain — i.e., the sequence becomes **bitonic** (non-decreasing then non-increasing, or monotonic).
- Filling a valley at position $ j $ requires raising $ h_j $ to at least $ \min(h_i, h_k) $, where $ (i, j, k) $ is a valley.
- The **total number of animals** needed to fill the landscape is the **minimum total elevation increase** required to eliminate all valleys.
**Given:**
- $ N, Q \in \mathbb{Z}^+ $, $ 1 \leq N, Q \leq 10^5 $
- Initial array $ h \in \mathbb{Z}_{\geq 0}^N $
- $ Q $ queries, each: $ (p_i, x_i) $, meaning $ h_{p_i} \gets h_{p_i} + x_i $ (persistent updates)
**Objective:**
For each query $ (p_i, x_i) $, after updating $ h_{p_i} $, compute the **minimum total elevation increase** required to eliminate all valleys in the current array $ h $, i.e., the **minimum total amount of "animals"** needed to make the sequence valley-free.
---
**Formal Problem:**
Let $ h^{(0)} = h $, and for each query $ t = 1, \dots, Q $, define:
$$
h^{(t)}_j =
\begin{cases}
h^{(t-1)}_j + x_t & \text{if } j = p_t \\
h^{(t-1)}_j & \text{otherwise}
\end{cases}
$$
For each $ t \in \{1, \dots, Q\} $, compute:
$$
A_t = \min_{\substack{h' \geq h^{(t)} \\ h' \text{ is valley-free}}} \sum_{i=1}^N (h'_i - h^{(t)}_i)
$$
where a sequence $ h' $ is **valley-free** if there do not exist indices $ i < j < k $ such that $ h'_i > h'_j < h'_k $.
---
**Equivalent Characterization:**
A sequence is valley-free **if and only if** it is **bitonic**: there exists an index $ m \in [1, N] $ such that:
- $ h'_1 \leq h'_2 \leq \dots \leq h'_m $
- $ h'_m \geq h'_{m+1} \geq \dots \geq h'_N $
Thus, the problem reduces to:
> For the current array $ h^{(t)} $, compute the minimum total increase $ \sum (h'_i - h^{(t)}_i) $ such that $ h' $ is bitonic and $ h' \geq h^{(t)} $.
This is a classic **minimum cost to make array bitonic** problem under non-decreasing constraints.
---
**Final Formal Statement:**
For each query $ t $, after updating $ h_{p_t} \gets h_{p_t} + x_t $, compute:
$$
\boxed{
\min_{\substack{h' \geq h \\ h' \text{ bitonic}}} \sum_{i=1}^N (h'_i - h_i)
}
$$
where $ h $ is the current state of the array, and “bitonic” means non-decreasing up to some peak, then non-increasing.
API Response (JSON)
{
"problem": {
"name": "J2. It's Raining Cats and Corgis (Hard Version)",
"description": {
"content": "*This is the hard version of the problem. The only difference between the two versions is the constraint on $x$. In this version, $x$ could be up to $10^5$.* It's raining cats and corgis! ... and a w",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CFJ2"
},
"statements": [
{
"statement_type": "Markdown",
"content": "*This is the hard version of the problem. The only difference between the two versions is the constraint on $x$. In this version, $x$ could be up to $10^5$.*\n\nIt's raining cats and corgis! ... and a w...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"*这是本题的困难版本。两个版本的唯一区别在于 $x$ 的约束。在本版本中，$x$ 最多可达 $10^5$。*\\n\\n天上正下着猫和柯基！……还有大量其他随机动物。\\n\\n作为一名动物学-气象学-地质学三重专业学生，你立即冲到野外研究这一现象。该野外区域是一个包含 $N$ 个位置的数组，其中第 $i^{\\\\text{th}}$ 个位置的...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ h = [h_1, h_2, \\dots, h_N] $ be the array of initial elevations.\n- A **valley** is a triple of indices $ (i, j, k) $ such that $ 1 \\leq i < j < k \\leq N $ and $ h_i > h_j < h...",
"is_translate": false,
"language": "Formal"
}
]
}