题目描述

难度分:$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;
}