CF1736C2 Good Subarrays (Hard Version)

这是本题的困难版本。在本版本中，你需要处理多个查询。注意，本版本中没有多组测试数据。只有当你同时解决了本题的两个版本时，才能进行 Hack。 一个长度为 $m$ 的数组 $b$ 被称为“好”的，当且仅当对于所有的 $i$，第 $i$ 个元素都满足 $b_i \geq i$。换句话说，$b$ 是“好”的当且仅当对于所有 $i$（$1 \leq i \leq m$），都有 $b_i \geq i$。 你会得到一个由 $n$ 个正整数组成的数组 $a$，并且你需要回答 $q$ 个查询。 每个查询给出两个整数 $p$ 和 $x$（$1 \leq p, x \leq n$）。你需要将 $a_p$ 赋值为 $x$（即 $a_p := x$）。在更新后的数组中，求有多少对下标 $(l, r)$，满足 $1 \leq l \leq r \leq n$，使得子数组 $[a_l, a_{l+1}, \ldots, a_r]$ 是“好”的。 注意，每个查询都是独立的，也就是说，每次查询后，数组 $a$ 都会恢复到初始状态。

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。 第三行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$），表示查询的数量。 接下来的 $q$ 行，每行包含两个整数 $p_j$ 和 $x_j$（$1 \leq p_j, x_j \leq n$），表示第 $j$ 个查询。

对于每个查询，输出在进行更改后，满足条件的下标对的数量。

以下是第一个样例的说明。 在第一个查询后，更新为 $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)$ 是满足条件的下标对。 由 ChatGPT 4.1 翻译