莫队2+值域分块

sccc_ · 2025-08-05 15:24:43 · 个人记录

P3834 【模板】可持久化线段树 2

因为 a_i \leq 10^9，但 n \leq 2 \times 10^5，因此对 a 数组进行离散化。

将 a copy 到 b 中，记录 f_x = a_i，代表离散化后下标 x 对应的是 a_i，且将 a_i 替换为其在 b 中去重后的下标 x。

令 cnt_x 为离散化后的值 x 在当前区间的出现次数，sum_{bl} 为第 bl 个块中所有元素的次数。

遍历每个块，用 sum 找到包含了第 k 小元素的块，再枚举这个块，用 cnt 找到这个元素即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m, num, len, ans[N], sum[N], cnt[N], a[N], b[N];
map<int, int> f;

struct query {
    int l, r, k, id;
} q[N];

bool cmp(query a, query b) {
    return (a.l / len == b.l / len ? a.r < b.r : a.l < b.l);
}

void add_sub(int x, int val) {
    int bl = x / num;
    cnt[x] += val;
    sum[bl] += val;
}

int rk(int k) {
    for (int i = 0; i <= num; i++) {
        if (k <= sum[i]) {
            for (int j = i * num; j <= (i + 1) * num; j++) {
                if (k <= cnt[j]) {
                    return j;
                } else {
                    k -= cnt[j];
                }
            }
        } else {
            k -= sum[i];
        }
    }
    return k + 1;
}

signed main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    len = sqrt(n);
    num = n / len + (n % len > 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort (b + 1, b + 1 + n);
    int length = unique(b + 1, b + 1 + n) - (b + 1);
    for (int i = 1; i <= n; i++) {
        int x = lower_bound(b + 1, b + 1 + length, a[i]) - b;
        f[x] = a[i];
        a[i] = x;
    }
    for (int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r >> q[i].k;
        q[i].id = i;
    }
    sort (q + 1, q + 1 + m, cmp);
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++) {
        while (l > q[i].l)
            add_sub(a[--l], 1);
        while (r < q[i].r)
            add_sub(a[++r], 1);
        while (l < q[i].l)
            add_sub(a[l++], -1);
        while (r > q[i].r)
            add_sub(a[r--], -1);
        ans[q[i].id] = f[rk(q[i].k)];
    }
    for (int i = 1; i <= m; i++)
        cout << ans[i] << '\n';
    return 0;
}

P4137 Rmq Problem / mex