题解：P14085 [ICPC 2023 Seoul R] Apricot Seeds

Egg_eating_master · 2025-09-28 14:22:39 · 题解

结论：长度为 n 的序列经过 k 轮冒泡后，下标区间 [1,p] 内的 p 个数，就是原序列中 [1,\min(p+k,n)] 内前 p 小的数。

证明：一方面，一个数在一轮冒泡过后，位置至多只会往左移动 1，所以在 k 轮冒泡后 [1,p] 内的数一定来自原序列的 [1,p+k] 这个区间。另一方面，如果把整个序列在 p+k 处截断，那么 k 轮冒泡后，最大的 k 个数一定会被移动到最后面的 k 个位置。于是证毕。

把询问看作两个前缀的答案相减，然后套用上面的结论，主席树维护即可。

::::info[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1000005;
int n, m, k, len;
int a[maxn], rt[maxn];
int ind[maxn];
struct SegTree {
    #define mid (l + r >> 1)
    int ls[maxn << 5], rs[maxn << 5], c[maxn << 5], s[maxn << 5], cnt;
    int update(int k, int l, int r, int qx) {
        int dir = ++cnt; ls[dir] = ls[k], rs[dir] = rs[k]; c[dir] = c[k] + 1, s[dir] = s[k] + ind[qx];
        if (l == r) return dir;
        if (qx <= mid) ls[dir] = update(ls[k], l, mid, qx);
        else rs[dir] = update(rs[k], mid + 1, r, qx);
        return dir;
    }
    int query(int p, int q, int l, int r, int v) {
        if (l == r) return v * ind[l];
        int w = c[ls[q]] - c[ls[p]];
        if (v <= w) return query(ls[p], ls[q], l, mid, v);
        else return query(rs[p], rs[q], mid + 1, r, v - w) + s[ls[q]] - s[ls[p]];
    }
} T;
void discrete() {
    for (int i = 1; i <= n; i++) ind[i] = a[i];
    sort(ind + 1, ind + 1 + n);
    len = unique(ind + 1, ind + 1 + n) - ind - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(ind + 1, ind + 1 + len, a[i]) - ind;
}
int kth(int l, int r, int k) {return T.query(rt[l - 1], rt[r], 1, len, k);}
int query(int l, int r, int k, int x) {return kth(l, min(r, l + x + k - 1), x);}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    discrete();
    for (int i = 1; i <= n; i++) rt[i] = T.update(rt[i - 1], 1, len, a[i]);
    for (int i = 1; i <= m; i++) {
        int l, r, k, x, y; cin >> l >> r >> k >> x >> y;
        cout << query(l, r, k, y) - query(l, r, k, x - 1) << '\n';
    }
    return 0;
}

::::