← 返回题目列表

Codeforces · 2009/G2

G2. 云里的子数组查询(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。在此版本中,保证所有查询的 $$$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])$$$。

输入

第一行包含 $$$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_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$$$。

示例

输入 #1

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

输出 #1

6
5
2
2
5
2
3

注意

在第一个测试用例的第二个查询中,我们计算以下函数值:

- $$$f([2,3,2,1,2])=3$$$,因为云里可以设置$$$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$$$ 移动中生成大小为 $$$5$$$ 的连续子数组(从位置 $$$2$$$ 开始)

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