{"raw_statement":[{"iden":"statement","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 whole bunch of other random animals.\n\nAs 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$.\n\nAs 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).\n\nYou wonder that if you increase the height of the landscape at position $i$ by $x$ units, how many animals will fill the resulting landscape.\n\nThe 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.\n\nThe 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.\n\nEach 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.\n\n*Note*: The changes made in each query should be preserved and taken into account when processing subsequent queries.\n\nPlease output $Q$ lines, where the $i^(t h)$ line contains the answer to the $i^(t h)$ query.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"Please output $Q$ lines, where the $i^(t h)$ line contains the answer to the $i^(t h)$ query."},{"iden":"examples","content":"Input10 42 1 4 4 5 2 3 4 5 33 17 14 15 1Output8\n7\n6\n6\nInput5 40 5 0 5 02 14 13 11 1Output5\n6\n5\n5\nInput6 20 0 0 0 0 02 14 1Output0\n1\n"},{"iden":"note","content":"  "}],"translated_statement":"[{\"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\":\"  \"}]}","sample_group":[],"show_order":[],"formal_statement":"**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_k $.\n- The landscape is **filled** when no valleys remain — i.e., the sequence becomes **bitonic** (non-decreasing then non-increasing, or monotonic).\n- 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.\n- The **total number of animals** needed to fill the landscape is the **minimum total elevation increase** required to eliminate all valleys.\n\n**Given:**\n\n- $ N, Q \\in \\mathbb{Z}^+ $, $ 1 \\leq N, Q \\leq 10^5 $\n- Initial array $ h \\in \\mathbb{Z}_{\\geq 0}^N $\n- $ Q $ queries, each: $ (p_i, x_i) $, meaning $ h_{p_i} \\gets h_{p_i} + x_i $ (persistent updates)\n\n**Objective:**\n\nFor 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.\n\n---\n\n**Formal Problem:**\n\nLet $ h^{(0)} = h $, and for each query $ t = 1, \\dots, Q $, define:\n\n$$\nh^{(t)}_j = \n\\begin{cases}\nh^{(t-1)}_j + x_t & \\text{if } j = p_t \\\\\nh^{(t-1)}_j & \\text{otherwise}\n\\end{cases}\n$$\n\nFor each $ t \\in \\{1, \\dots, Q\\} $, compute:\n\n$$\nA_t = \\min_{\\substack{h' \\geq h^{(t)} \\\\ h' \\text{ is valley-free}}} \\sum_{i=1}^N (h'_i - h^{(t)}_i)\n$$\n\nwhere a sequence $ h' $ is **valley-free** if there do not exist indices $ i < j < k $ such that $ h'_i > h'_j < h'_k $.\n\n---\n\n**Equivalent Characterization:**\n\nA sequence is valley-free **if and only if** it is **bitonic**: there exists an index $ m \\in [1, N] $ such that:\n\n- $ h'_1 \\leq h'_2 \\leq \\dots \\leq h'_m $\n- $ h'_m \\geq h'_{m+1} \\geq \\dots \\geq h'_N $\n\nThus, the problem reduces to:\n\n> 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)} $.\n\nThis is a classic **minimum cost to make array bitonic** problem under non-decreasing constraints.\n\n---\n\n**Final Formal Statement:**\n\nFor each query $ t $, after updating $ h_{p_t} \\gets h_{p_t} + x_t $, compute:\n\n$$\n\\boxed{\n\\min_{\\substack{h' \\geq h \\\\ h' \\text{ bitonic}}} \\sum_{i=1}^N (h'_i - h_i)\n}\n$$\n\nwhere $ h $ is the current state of the array, and “bitonic” means non-decreasing up to some peak, then non-increasing.","simple_statement":null,"has_page_source":false}