题目描述

这是问题的极限版本。在这个版本中，每个查询的输出与简单版和困难版不同。保证对于所有的查询都有 $r \geq l+k-1$。

对于一个任意数组 $b$，云莉可以无数次进行以下操作：

• 选择一个下标 $i$，将 $b_i$ 设置为任意她想要的整数 $x$（$x$ 不限制在 $[1, n]$ 区间内）。

定义 $f(b)$ 为所需的最小操作次数，以使得 $b$ 中存在一个长度至少为 $k$ 的连续子数组。

云莉给出一个大小为 $n$ 的数组 $a$ 并询问你 $q$ 次，你需要在每次查询中计算并输出 $\sum_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f([a_i, a_{i+1}, \ldots, a_j])$。

如果数组中存在从下标 $i$ 开始的长度为 $k$ 的连续子数组（$1 \leq i \leq |b|-k+1$），那么在该子数组中，对于 $i < j \leq i+k-1$，必须满足 $b_j = b_{j-1} + 1$。

输入格式

第一行输入 $t$（$1 \leq t \leq 10^4$）—— 表示测试用例的数量。

接下来的每个测试用例的第一行包含三个整数 $n$、$k$ 和 $q$（$1 \leq k \leq n \leq 2 \cdot 10^5$，$1 \leq q \leq 2 \cdot 10^5$），分别表示数组的长度、连续子数组的长度和查询的次数。

接下来是一行，包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。

接下来的 $q$ 行中，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$，$r \geq l+k-1$），表示查询的区间。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，所有测试用例中 $q$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个查询，输出一行结果，即 $\sum_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f([a_i, a_{i+1}, \ldots, a_j])$。

样例

5
7 2 4
1 2 3 2 1 2 3
4 6
1 7
2 7
3 7
8 4 2
4 3 1 1 2 4 3 2
3 6
1 5
5 4 2
4 5 1 2 3
1 4
1 5
10 4 8
2 3 6 5 8 9 8 10 10 1
2 7
6 10
1 9
1 6
3 9
4 10
2 10
1 8
10 7 4
3 4 5 3 4 5 9 10 8 9
1 9
2 10
1 10
2 9

1
3
3
3
2
7
2
4
8
6
28
7
16
20
32
19
18
15
26
9

样例说明

在第一个测试用例的第一个查询中，我们可以通过如下方法来计算结果：

• 当 $i = 4$ 且 $j = 5$ 时，$f([2, 1])=1$，因为云莉可以将 $b_2$ 设为 3，从而一步操作后形成长度为 2 的连续子数组。
• 当 $i = 4$ 且 $j = 6$ 时，$f([2, 1, 2])=0$，因为已经存在长度为 2 的连续子数组。
• 当 $i = 5$ 且 $j = 6$ 时，$f([1, 2])=0$，因为已经存在长度为 2 的连续子数组。

此查询的答案为 $1+0+0=1$。

本翻译由 AI 自动生成

来源

Codeforces 2009G3，英文题名 Yunli's Subarray Queries (extreme version)。