Good Subarrays (Hard Version)

题意翻译

这题是 CF1936C1 的困难版。 我们定义一个数组 $b$ 是好的当且仅当所有的 $b_i \ge i$。 现在给你 $q$ 次操作，每次操作有两个数 $p$ 和 $x$，问把 $a_p$ 赋值成 $x$ 后 $a$ 数组好的子序列（**这些子序列必须连续**）的个数。 数据范围： + $1 \le n \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$。 + $1 \le a_i \le n$，$1 \le p_j,x_j \le n$。 $\verb!by!$ [Tx_Lcy](https://www.luogu.com.cn/user/253608)

题目描述

This is the hard version of this problem. In this version, we have queries. Note that we do not have multiple test cases in this version. You can make hacks only if both versions of the problem are solved. An array $ b $ of length $ m $ is good if for all $ i $ the $ i $ -th element is greater than or equal to $ i $ . In other words, $ b $ is good if and only if $ b_i \geq i $ for all $ i $ ( $ 1 \leq i \leq m $ ). You are given an array $ a $ consisting of $ n $ positive integers, and you are asked $ q $ queries. In each query, you are given two integers $ p $ and $ x $ ( $ 1 \leq p,x \leq n $ ). You have to do $ a_p := x $ (assign $ x $ to $ a_p $ ). In the updated array, find the number of pairs of indices $ (l, r) $ , where $ 1 \le l \le r \le n $ , such that the array $ [a_l, a_{l+1}, \ldots, a_r] $ is good. Note that all queries are independent, which means after each query, the initial array $ a $ is restored.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ). The third line contains an integer $ q $ ( $ 1 \leq q \leq 2 \cdot 10^5 $ ) — the number of queries. Each of the next $ q $ lines contains two integers $ p_j $ and $ x_j $ ( $ 1 \leq p_j, x_j \leq n $ ) – the description of the $ j $ -th query.

输出格式

For each query, print the number of suitable pairs of indices after making the change.

输入输出样例

输入样例 #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

说明

Here are notes for first example. In first query, after update $ a=[2,4,1,4] $ . Now $ (1,1) $ , $ (2,2) $ , $ (3,3) $ , $ (4,4) $ , $ (1,2) $ , and $ (3,4) $ are suitable pairs. In second query, after update $ a=[2,4,3,4] $ . Now all subarrays of $ a $ are good. In third query, after update $ a=[2,1,1,4] $ . Now $ (1,1) $ , $ (2,2) $ , $ (3,3) $ , $ (4,4) $ , and $ (3,4) $ are suitable.

**题目大意：**

这个问题是 CF1936C1 的困难版本。在这个版本中，我们定义一个数组 $ b $ 是好的当且仅当所有的 $ b_i \ge i $。给定一个由 $ n $ 个正整数组成的数组 $ a $，并询问 $ q $ 个查询。在每次查询中，给出两个整数 $ p $ 和 $ x $，要求将 $ a_p $ 赋值为 $ x $，然后找出在更新后的数组中，有多少对索引 $ (l, r) $（其中 $ 1 \le l \le r \le n $），使得数组 $ [a_l, a_{l+1}, \ldots, a_r] $ 是好的。所有的查询都是独立的，这意味着在每个查询之后，初始数组 $ a $ 都会被恢复。

**输入输出数据格式：**

**输入格式：**

- 第一行包含一个整数 $ n $（$ 1 \le n \le 2 \times 10^5 $）。
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le n $）。
- 第三行包含一个整数 $ q $（$ 1 \le q \le 2 \times 10^5 $）——查询的数量。
- 接下来的 $ q $ 行，每行包含两个整数 $ p_j $ 和 $ x_j $（$ 1 \le p_j, x_j \le 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) $ 是合适的索引对。**题目大意：** 这个问题是 CF1936C1 的困难版本。在这个版本中，我们定义一个数组 $ b $ 是好的当且仅当所有的 $ b_i \ge i $。给定一个由 $ n $ 个正整数组成的数组 $ a $，并询问 $ q $ 个查询。在每次查询中，给出两个整数 $ p $ 和 $ x $，要求将 $ a_p $ 赋值为 $ x $，然后找出在更新后的数组中，有多少对索引 $ (l, r) $（其中 $ 1 \le l \le r \le n $），使得数组 $ [a_l, a_{l+1}, \ldots, a_r] $ 是好的。所有的查询都是独立的，这意味着在每个查询之后，初始数组 $ a $ 都会被恢复。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 $ n $（$ 1 \le n \le 2 \times 10^5 $）。 - 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le n $）。 - 第三行包含一个整数 $ q $（$ 1 \le q \le 2 \times 10^5 $）——查询的数量。 - 接下来的 $ q $ 行，每行包含两个整数 $ p_j $ 和 $ x_j $（$ 1 \le p_j, x_j \le 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) $ 是合适的索引对。