题目描述
难度分:$2200$
输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$q$之和$\leq 2 \times 10^5$。
每组数据输入$n$、$k(1 \leq k \leq n \leq 2 \times 10^5)$、$q(1 \leq q \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n)$。
对于一个数组$b$，你可以执行若干次操作，每次操作可以把一个$b[i]$改成任意值。
定义$f(b)$表示使$b$中存在长度至少为$k$的连续递增子数组的最小操作次数。（连续递增：对任意$i$满足$b[i+1] = b[i] + 1$）
然后输入$q$个询问，每个询问输入$l$和$r$，下标从$1$开始，保证$r-l+1 \geq k$。
定义$a[i..j]$表示$a$的下标从$i$到$j$的子数组。对于每个询问，输出$f(a[l..l+k-1]) + f(a[l..l+k]) + … + f(a[l..r])$。
输入样例
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
算法
单调栈+倍增
这题感觉真的很难，不是很懂怎么在$div4$出现，而且灵佬还拿来当成周四的茶。
连续递增，等价于对任意的$i \leq j$都有$a[j]=a[i]+(j-i)$成立，即$a[j]-j=a[i]-i$。所以把$a[i]$变成$a[i]-i$，这样「连续递增」就变成了「元素值都相等」。
首先，跑一个定长滑动窗口，计算每个长为$k$的子数组的众数出现次数，那么「$k$-众数出现次数」就是这个子数组最少需要修改的元素个数。用一个$counter$统计窗口内的元素频数，另一个有序集合$tup$记录$counter$中的键值对。这两个数据结构辅助，然后滑动窗口就能得到每个长度为$k$的窗口$a[i…i+k-1]$的$f$值。
每个子数组的「$k$-众数出现次数」记录在一个长为$n-k+1$的数组$mn$中。接下来就发现一个很隐秘的事实：
- 一个长为$k+1$的子数组的$f$值，等于其内部$2$个长为$k$的子数组的「$k$-众数出现次数」的最小值。
- 一个长为$k+2$的子数组的$f$值，等于其内部$3$个长为$k$的子数组的「$k$-众数出现次数」的最小值。
……
这样对于每个询问$[l,r]$，我们求子数组$a[l…l+k-1]$、$a[l+1…l+k]$、……、$a[r-k+1…r]$最小操作数的累加和即可。但如果直接遍历这些区间的话时间复杂度就太高了，可以用倍增来优化。$f[i][j]$表示$mn[i]$后第$2^j$个比$mn[i]$小的数的索引，$s[i][j]$表示$i$到$f[i][j]$之前对应子数组最小操作数的累加和。$f[i][0]$可以用单调栈求出来，而$s[i][0]=(f[i][0]-i) \times mn[i]$，接下来用倍增的预处理计算出整个$f$和$s$数组。
而对于每个询问$[l,r]$，利用$f$数组，以二进制的方式来遍历$[l…l+k-1]$、$[l+1…l+k]$、……、$[r-k+1…r]$这些子数组，利用$s$数组求出这些最小操作数之和就可以了。说得简单，但如果对倍增理解不够深刻的话写起来也挺晕的。
复杂度分析
时间复杂度
预处理出$mn$需要滑动窗口遍历整个数组$a$，时间复杂度为$O(n)$。对于每个窗口，需要维护有序集合$tup$中的二元组，存在删除和插入操作，时间复杂度为$O(log_2n)$。所以这一步的时间复杂度为$O(nlog_2n)$。
接下来单调栈+倍增预处理出$s$和$f$两个数组，由于询问$[l,r]$的极限区间长度就是$O(n)$级别的，所以这一步预处理的时间复杂度为$O(nlog_2n)$。
最后处理每个询问，每个询问都要用二进制的方式来凑$r-l+1$级别的长度，最差情况下为$O(n)$长度的区间。而用二进制来凑这个长度就是$O(log_2n)$，所以处理所有询问的总时间复杂度就是$O(qlog_2n)$。
综上，整个算法的时间复杂度为$O((n+q)log_2n)$。
空间复杂度
空间消耗的瓶颈在于两个$ST$表$s$和$f$，空间消耗就是$O(nlog_2n)$。$mn$、$counter$、$tup$这几个数据结构中存储的元素数量最多就是$O(n)$级别。所以整个算法的额外空间复杂度为$O(nlog_2n)$。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 200010, K = 18;
int T, n, k, q, a[N], mn[N];
LL f[N][K], s[N][K];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &n, &k, &q);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i] -= i;
}
map<int, int> counter;
for(int i = 1; i <= k; i++) {
counter[a[i]]++;
}
set<PII> tup;
for(auto&[num, cnt]: counter) {
tup.insert({cnt, num});
}
int freq = tup.rbegin()->first, mode = tup.rbegin()->second;
mn[1] = k - freq;
for(int i = k + 1; i <= n; i++) {
int j = i - k;
int val = a[j];
int oldfreq = counter[a[j]];
tup.erase({oldfreq, val});
counter[a[j]]--;
if(counter[a[j]] == 0) {
counter.erase(a[j]);
}else {
tup.insert({counter[a[j]], a[j]});
}
oldfreq = counter[a[i]];
tup.erase({oldfreq, a[i]});
counter[a[i]]++;
tup.insert({oldfreq + 1, a[i]});
freq = tup.rbegin()->first, mode = tup.rbegin()->second;
mn[i - k + 1] = k - freq;
}
// 单调栈求每个mn[i]下一个更小数的位置
stack<int> stk;
for(int i = n; i >= 1; i--){
while(stk.size() && mn[stk.top()] >= mn[i]) {
stk.pop();
}
f[i][0] = stk.size()? stk.top(): n + 1;
s[i][0] = (f[i][0] - i) * mn[i];
stk.push(i);
}
for(int i = 0; i < K; i++) {
f[n + 1][i] = n + 1;
}
for(int j = 1; j < K; j++) {
for(int i = 1; i <= n; i++){
f[i][j] = f[f[i][j - 1]][j - 1];
s[i][j] = s[i][j - 1] + s[f[i][j - 1]][j - 1];
}
}
while(q--) {
int l, r;
scanf("%d%d", &l, &r);
r = r - k + 1;
LL ans = 0;
// 用二进制来凑这个r-l+1的距离
for(int i = K - 1; i >= 0; i--) {
if(f[l][i] <= r) {
ans += s[l][i];
l = f[l][i];
}
}
ans += (r - l + 1LL) * mn[l];
printf("%lld\n", ans);
}
}
return 0;
}
