CF2009G3 Yunli's Subarray Queries (extreme version)

这是问题的极限版本。在这个版本中，每个查询的输出与简单版和困难版不同。保证对于所有的查询都有 $ 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])$。

在第一个测试用例的第一个查询中，我们可以通过如下方法来计算结果： - 当 $ 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 自动生成**