codeforces#P2009G2. Yunli's Subarray Queries (hard version)
Yunli's Subarray Queries (hard version)
Description
This is the hard version of the problem. In this version, it is guaranteed that $r \geq l+k-1$ for all queries.
For an arbitrary array $b$, Yunli can perform the following operation any number of times:
- Select an index $i$. Set $b_i = x$ where $x$ is any integer she desires ($x$ is not limited to the interval $[1,n]$).
Denote $f(b)$ as the minimum number of operations she needs to perform until there exists a consecutive subarray$^{\text{∗}}$ of length at least $k$ in $b$.
Yunli is given an array $a$ of size $n$ and asks you $q$ queries. In each query, you must output $\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$.
$^{\text{∗}}$If there exists a consecutive subarray of length $k$ that starts at index $i$ ($1 \leq i \leq |b|-k+1$), then $b_j = b_{j-1} + 1$ for all $i < j \leq i+k-1$.
The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains three integers $n$, $k$, and $q$ ($1 \leq k \leq n \leq 2 \cdot 10^5$, $1 \leq q \leq 2 \cdot 10^5$) — the length of the array, the length of the consecutive subarray, and the number of queries.
The following line contains $n$ integers $a_1, a_2, ..., a_n$ ($1 \leq a_i \leq n$).
The following $q$ lines contain two integers $l$ and $r$ ($1 \leq l \leq r \leq n$, $r \geq l+k-1$) — the bounds of the query.
It is guaranteed the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ and the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.
Output $\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$ for each query on a new line.
Input
The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains three integers $n$, $k$, and $q$ ($1 \leq k \leq n \leq 2 \cdot 10^5$, $1 \leq q \leq 2 \cdot 10^5$) — the length of the array, the length of the consecutive subarray, and the number of queries.
The following line contains $n$ integers $a_1, a_2, ..., a_n$ ($1 \leq a_i \leq n$).
The following $q$ lines contain two integers $l$ and $r$ ($1 \leq l \leq r \leq n$, $r \geq l+k-1$) — the bounds of the query.
It is guaranteed the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ and the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.
Output
Output $\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$ for each query on a new line.
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
6
5
2
2
5
2
3
Note
In the second query of the first testcase, we calculate the following function values:
- $f([2,3,2,1,2])=3$ because Yunli can set $b_3=4$, $b_4=5$, and $b_5=6$, making a consecutive subarray of size $5$ in $3$ moves.
- $f([2,3,2,1,2,3]=2$ because we can set $b_3=0$ and $b_2=-1$, making a consecutive subarray of size $5$ in $2$ moves (starting at position $2$)
The answer to this query is $3+2=5$.