CF2009G3.Yunli's Subarray Queries (extreme version)

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

输入输出样例

输入#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

说明/提示

在第一个测试用例的第一个查询中，我们可以通过如下方法来计算结果：

当 $ 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 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页