← 返回题目列表

Codeforces · 1736/C2

C2. 好的子数组(硬版)

中文机器翻译题面 查看原题

这是这个问题的困难版本。在这个版本中,我们有疑问。请注意,我们在此版本中没有多个测试用例。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

如果对于所有 $$$i$$$,第 $$$i$$$ 个元素大于或等于 $$$i$$$,则长度为 $$$m$$$ 的数组 $$$b$$$ 是好的。换句话说,$$$b$$$ 是好的当且仅当 $$$b_i \geq i$$$ 对于所有 $$$i$$$ ($$$1 \leq i \leq m$$$)。

给您一个由 $$$n$$$ 正整数组成的数组 $$$a$$$,并询问您 $$$q$$$ 查询。

在每个查询中,都会给出两个整数 $$$p$$$ 和 $$$x$$$ ($$$1 \leq p,x \leq n$$$)。您必须执行 $$$a_p := x$$$ (将 $$$x$$$ 分配给 $$$a_p$$$)。在更新后的数组中,找到索引对 $$$(l, r)$$$ 的数量,其中 $$$1 \le l \le r \le n$$$,这样数组 $$$[a_l, a_{l+1}, \ldots, a_r]$$$ 就是好的。

请注意,所有查询都是独立的,这意味着每次查询后,都会恢复初始数组$$$a$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。

第三行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含两个整数 $$$p_j$$$ 和 $$$x_j$$$ ($$$1 \leq p_j, x_j \leq n$$$) – 第 $$$j$$$ 查询的描述。

输出

对于每个查询,在进行更改后打印合适的索引对的数量。

示例

输入 #1

4
2 4 1 4
3
2 4
3 3
2 1

输出 #1

6
10
5

输入 #2

5
1 1 3 2 1
3
1 3
2 5
4 5

输出 #2

7
9
8

注意

以下是第一个示例的注释。

在第一个查询中,更新 $$$a=[2,4,1,4]$$$ 后。现在 $$$(1,1)$$$、$$$(2,2)$$$、$$$(3,3)$$$、$$$(4,4)$$$、$$$(1,2)$$$ 和 $$$(3,4)$$$ 是合适的对。

在第二个查询中,更新 $$$a=[2,4,3,4]$$$ 后。现在 $$$a$$$ 的所有子数组都很好。

在第三个查询中,更新 $$$a=[2,1,1,4]$$$ 后。现在 $$$(1,1)$$$、$$$(2,2)$$$、$$$(3,3)$$$、$$$(4,4)$$$ 和 $$$(3,4)$$$ 是合适的。