题目描述

这是问题的困难版本。在此版本中，保证所有查询的 $r\geq l+k-1$。

对于任意数组 $b$，Yunli 可以执行以下操作任意次数：

• 选择一个索引 $i$。设置 $b_i=x$，其中 $x$ 是她想要的任何整数（$x$ 不限于区间 $[1,n]$）。

将 $f(b)$ 表示为她需要执行的最小操作数，直到 $b$ 中存在长度至少为 $k$ 的连续子数组$^{\text{*}}$。

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

$^{\text{*}}$ 如果存在一个长度为 $k$ 的连续子数组，从索引 $i$ 开始（$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 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_{j=l+k-1}^{r}f([a_l,a_{l+1},\ldots,a_j])$。

样例

3
7 5 3
1 2 3 2 1 2 3
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

6
5
2
2
5
2
3

样例说明

在第一组测试用例的第二次查询中，我们计算了以下函数值：

• $f([2,3,2,1,2])=3$，因为 Yunli 可以设置 $b_3=4$、$b_4=5$ 和 $b_5=6$，从而在 $3$ 次操作中形成一个大小为 $5$ 的连续子阵列。
• $f([2,3,2,1,2,3])=2$，因为我们可以设置 $b_3=0$ 和 $b_2=-1$，在 $2$ 次操作中中（从位置 $2$ 开始）形成一个大小为$5$的连续子阵列。

这个查询的答案是 $3+2=5$。

翻译 @Cure_Wing。

来源

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