← 返回题目列表

Codeforces · 2009/G1

G1. 云里的子数组查询(简易版)

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

这是问题的简单版本。在此版本中,保证所有查询$$$r=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])$$$。请注意,在此版本中,您只需输出 $$$f([a_l, a_{l+1}, \ldots, a_{l+k-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, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$)。

以下 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$, $$$r=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 5
2 6
3 7
8 4 2
4 3 1 1 2 4 3 2
3 6
2 5
5 4 2
4 5 1 2 3
1 4
2 5

输出 #1

2
3
2
2
2
2
1

注意

在第一个测试用例的第一个查询中,$$$b=[1,2,3,2,1]$$$。云里可以在$$$2$$$移动中生成长度为$$$5$$$的连续子数组:

- 设置$$$b_4=4$$$
- 设置$$$b_5=5$$$

在第一个测试用例的第二个查询中,$$$b=[2,3,2,1,2]$$$。云里可以在 $$$3$$$ 移动中生成长度为 $$$5$$$ 的连续子数组:

- 设置$$$b_3=0$$$
- 设置$$$b_2=-1$$$
- 设置$$$b_1=-2$$$