这是问题的极端版本。在此版本中,每个查询的输出与简单版本和困难版本不同。还保证所有查询的 $$$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_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f([a_i, a_{i+1}, \ldots, a_j])$$$。
输入
第一行包含 $$$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, ..., 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])$$$。
示例
输入 #1
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
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$$$,使得 $$$1$$$ 移动一个大小为 $$$2$$$ 的连续子数组。
- $$$i = 4$$$ 和 $$$j = 6$$$: $$$f([2, 1, 2])=0$$$ 因为已经有一个大小为 $$$2$$$ 的连续数组。
- $$$i = 5$$$ 和 $$$j = 6$$$: $$$f([1, 2])=0$$$ 因为已经有一个大小为 $$$2$$$ 的连续数组。
该查询的答案是$$$1+0+0=1$$$。