CF2009G2 Yunli's Subarray Queries (hard version)

首先考虑计算 \(f([a_1, a_2,\cdots,a_k])\)：发现对于在同一条斜线上的 \(a_i\), \(a_i-i\) 的值是相同的。统计出 \(a_i-i\) 的众数 \(x\)，则 \(k-x\) 次操作就可以将这一段变成连续数组。

处理好了第一个长度为 \(k\) 的段，向右滑动窗口，只需要把左侧出去的 \(a_1-1\) 出现次数减 1，右侧进来的 \(a_{k+1}-(k+1)\) 出现次数加 1，就可以动态维护上文的众数 \(x\) 了。具体实现上，我们可以用一个 map 维护窗口中 \(a_i-i\) 各种取值的出现次数，把这些出现次数扔进 multiset，最大值 *s.rbegin() 就是 \(a_i-i\) 的众数。到这里，我们用 \(O(n\log n)\) 的复杂度求出每个长度为 \(k\) 的窗口的最小操作数，easy version 就做完了。

hard version 式子的意思可以理解为：对于给定的询问 \(l,r\)，要在区间的每个长度大于 \(k\) 的前缀上——第一个前缀长度为 \(k\)，包含了一个完整窗口；第二个长度为 \(k+1\)，包含了两个窗口，依此类推——对每个窗口的最小操作数求一次 \(\min\)。

为此，我们先把询问离线下来，按区间左端点排序，然后从后往前遍历每个长度为 \(k\) 的窗口，扔进一个单调栈里。如果当前窗口 \(i\) 的操作数 \(x\) 比栈顶的窗口大，则放在栈顶，并在线段树上的位置 \(i\) 单点加 \(x\)；如果操作数小，就弹栈，直到栈顶窗口 \(top\) 的操作数 \(x_{top} < x\)，然后在线段树上从 \(i\) 到 \(top-1\) 区间赋值 \(x\) (具体实现上两种情况可以合并，一个都弹不了则区间为 \([i,i]\))。随后，检查是否有询问的左端点 \(l=i\)，把这些询问一一处理（线段树区间 \(\min\)）。这一部分的复杂度 \(O(n\log n+q)\)，这道题就完成了。

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i <= b; i++)
#define dep(i, a, b) for (int i = a; i >= b; i--)
#define endl '\n'

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;

struct seg {
    vi L, R, tag;
    vll sum;

#define ls p << 1
#define rs p << 1 | 1
#define mid ((L[p] + R[p]) >> 1)

    seg(int n)
        : L(n * 4 + 10), R(n * 4 + 10), sum(n * 4 + 10), tag(n * 4 + 10) {
        bld(1, 1, n);
    }

    void up(int p) { sum[p] = sum[ls] + sum[rs]; }

    void bld(int p, int l, int r) {
        L[p] = l, R[p] = r, tag[p] = -1;
        if (l == r) return;
        bld(ls, l, mid);
        bld(rs, mid + 1, r);
        up(p);
    }

    void atg(int p, ll v) { tag[p] = v, sum[p] = v * (R[p] - L[p] + 1); }

    void pd(int p) {
        if (tag[p] == -1) return;
        atg(ls, tag[p]), atg(rs, tag[p]);
        tag[p] = -1;
    }

    void upd(int p, int l, int r, int v) {
        if (l <= L[p] && R[p] <= r) return atg(p, v), void();
        pd(p);
        if (l <= mid) upd(ls, l, r, v);
        if (r > mid) upd(rs, l, r, v);
        up(p);
    }

    ll ask(int p, int l, int r) {
        if (l <= L[p] && R[p] <= r) return sum[p];
        pd(p);
        ll res = 0;
        if (l <= mid) res += ask(ls, l, r);
        if (r > mid) res += ask(rs, l, r);
        return res;
    }

#undef ls
#undef rs
#undef mid
};

struct qry {
    int l, r, id;
    bool operator<(const qry& o) const {
        return l < o.l;
    }
};

void solve() {
    int n, k, m;
    cin >> n >> k >> m;
    vi a(n + 1);
    rep(i, 1, n) cin >> a[i];
    map<int, int> mp;
    multiset<int> s;
    rep(i, 1, n) s.insert(0);
    rep(i, 1, k - 1) {
        s.erase(s.find(mp[a[i] - i]));
        mp[a[i] - i]++;
        s.insert(mp[a[i] - i]);
    }
    int K = n - k + 1;
    vi c(K + 1);
    rep(i, k, n) {
        s.erase(s.find(mp[a[i] - i]));
        mp[a[i] - i]++;
        s.insert(mp[a[i] - i]);
        int p = i - k + 1;
        c[p] = k - *s.rbegin();
        s.erase(s.find(mp[a[p] - p]));
        mp[a[p] - p]--;
        s.insert(mp[a[p] - p]);
    }
    vector<qry> q(m + 1);
    rep(i, 1, m) {
        q[i].id = i;
        cin >> q[i].l >> q[i].r;
    }
    sort(q.begin() + 1, q.end());
    seg tr(K);      // i维护前缀l~i最小步数
    stack<int> st;  // 单调栈
    vll ans(m + 1);
    int j = m;
    dep(i, K, 1) {
        while (!st.empty() && c[st.top()] >= c[i]) st.pop();
        int end = st.empty() ? K : st.top() - 1;
        st.push(i);
        tr.upd(1, i, end, c[i]);
        for (; j && q[j].l == i; j--)
            ans[q[j].id] = tr.ask(1, q[j].l, q[j].r - k + 1);
    }
    rep(i, 1, m) cout << ans[i] << endl;
}

int32_t main(int t = 1) {
    cin >> t;
    while (t--) solve();
}