← 返回题目列表

Codeforces · 2009/G3

G3. 云里的子数组查询(极限版)

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

这是问题的极端版本​​。在此版本中,每个查询的输出与简单版本和困难版本不同。还保证所有查询的 $$$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$$$。