CF2009G2 Yunli's Subarray Queries (hard version) Solution

冷却心 · 2024-11-25 17:12:15 · 题解

对于一个满足条件的数组 \{a\}，我们对每个数加上 n-i 那么就可以得到一个新数组 \{b\}，其中 b_i=a_i+n-i，因为 a_i+1=a_{i+1}，那么：

\begin{aligned}b_i&=a_i+n-i,\\b_{i+1}=a_{i+1}+n-(i+1)&=a_i+1+n-i-1=a_i+n-i,\\ b_i=b_{i+1}\end{aligned}

也就是 b 数组完全相同。所以对于一个并不满足条件的长度为 l 的数组，如果对它进行以上的变换之后，众数的个数是 k，则把它合法化的最少操作次数就是 l-k。

首先我们发现这道题是静态的。我们记 g_i 表示把子数组 a_i,a_{i+1},\cdots,a_{i+k-1} 这一段合法化的最小操作次数。这比较类似一个滑动窗口，根据上面引用内的性质，我们可以用一个 map 或者权值线段树 O(n\log n) 求出所有的 g_i。所以题目定义的函数就是：

即取这么多子区间中最小的一个答案。所以对于一次询问 l, r，要求的和式就是：

即一个从 l 开始的前缀最小值连续和。我们发现这个并不好维护。我们考虑一个答案 g_i 能影响到的区间。首先我们发现，对于某一个 g_i，它能影响到的区间最远可以到达下一个比他小的 g_j 之前（或者数组结尾）。那么我们处理一个 \{p\} 数组，p_i 表示下一个小于 g_i 的数的位置（如果没有则为 n+1），这个可以单调栈 O(n) 求出。然后思考如何求答案。

设当前询问左右端点分别为 x,y，而前缀求值的右端点是 y-k+1，我们不妨把 y 赋值为它。我们使用一个变量 t，表示当前位置，一开始为 x。那么前缀最小值为它的区间就是从 t 到 p_t-1 的区间，对答案的贡献是 g_t\times (p_t-t)，然后把 t:= p_t 向后跳。直到跳到右端点 y。然后贡献直接累加后输出即可。

暴力跳是 O(n) 的，可以使用倍增变成预处理 O(n\log n)，查询 O(\log n)。

总时间复杂度是 O(n\log n)。

#include <bits/stdc++.h>
#define LL long long
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n, K, Q, A[N], ret[N];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int tree[N << 2];
void pushup(int p) { tree[p] = max(tree[ls(p)], tree[rs(p)]); }
void build(int p, int l, int r) {
    tree[p] = -1e9; if (l == r) return ;
    int mid = (l + r) >> 1; build(ls(p), l, mid); build(rs(p), mid + 1, r);
    return ;
}
void update(int p, int l, int r, int x, int k) {
    if (x > r || x < l) return ;
    if (l == r) { 
        if (tree[p] == -1e9) tree[p] = 0; 
        tree[p] += k; 
        if (tree[p] == 0) tree[p] = -1e9;
        return ;
    }
    int mid = (l + r) >> 1; update(ls(p), l, mid, x, k); update(rs(p), mid + 1, r, x, k);
    pushup(p); return ;
}
int stk[N], tp = 0, fa[N][20]; LL sum[N][20];
signed main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int _; cin >> _;
    while (_ --) {
        cin >> n >> K >> Q;
        for (int i = 1; i <= n; A[i] += n - i, i ++) cin >> A[i];
        build(1, 1, n * 2);
        for (int i = 1; i < K; i ++) update(1, 1, n * 2, A[i], 1);
        for (int i = 1; i <= n - K + 1; i ++) {
            update(1, 1, n * 2, A[i + K - 1], 1); ret[i] = K - tree[1]; update(1, 1, n * 2, A[i], -1);
        } tp = 0; ret[n - K + 2] = -1;
        for (int i = 1; i <= n - K + 2; i ++) {
            while (tp && ret[stk[tp]] >= ret[i]) {
                fa[stk[tp]][0] = i; sum[stk[tp]][0] = 1ll * (i - stk[tp]) * ret[stk[tp]]; tp --;
            } stk[++ tp] = i;
        }fa[n - K + 2][0] = n - K + 2; sum[n - K + 2][0] = 0;
        for (int k = 1; k <= 19; k ++) for (int i = 1; i <= n - K + 2; i ++)
            fa[i][k] = fa[fa[i][k - 1]][k - 1], sum[i][k] = sum[i][k - 1] + sum[fa[i][k - 1]][k - 1];
        int x, y;
        while (Q --) {
            cin >> x >> y;
            LL Ans = 0; int cur = x; y = y - K + 1;
            for (int i = 19; i >= 0; i --) if (fa[cur][i] <= y)
                Ans += sum[cur][i], cur = fa[cur][i];
            Ans += (y - cur + 1) * ret[cur]; cout << Ans << "\n";
        }
    }
    return 0;
}