题解：SP9055 FREQ2 - Most Frequent Value

Charllote_ · 2025-03-17 20:33:20 · 题解

题解：SP9055 FREQ2 - Most Frequent Value

关于此题

首先我们看到这是一道 spoj 的题，这就注定了它是卡常的。发现这道题与蒲公英很像，然后就被卡常了。所以这道题不能用普通的分块做。

思路

说明 L(i)、R(i)、ID(i) 分别表示第 i 块的左端点、右端点和第 i 个数在那个块。

普通分块（TLE）

块长为 \sqrt{n}。因为值域太大所以要进行离散化。

维护两个数组分别是 q[i][j] 和 md[i][j] 分别表示在前 i 个块中值为 j 的数出现的个数与在第 i \sim j 的块中的众数是谁。

我们发现在 l \sim r 中影响众数的地方在 l \sim R(ID(l))、L(ID(r)) \sim r。所以我们只要暴力枚举这两块直接的数，直接增加打擂台即可。

时间复杂度：\Theta (n\sqrt{n})（常数过大）

莫队（AC）

发现这道题与蒲公英不同的地方在于：

它没有强制在线
它只需要求出现次数

所以考虑莫队。

同普通分块一样需要离散化，块长为 \sqrt{n}。由于指针要来回跑所以要把查询按左端点所在的块排序，同一块内的查询按右端点排序。

使用两个指针 curl 和 curr 表示当前处理的区间。通过移动指针来调整当前区间，同时维护一个计数数组 cnt 和一个频率数组 freq。cnt[x] 表示当前区间中整数 x 的出现次数。freq[k] 表示当前区间中出现次数为 k 的整数的个数。

对于每个查询，通过移动指针 curl 和 curr 来调整当前区间，使其与查询区间一致。在移动指针的过程中，更新 cnt 和 freq 数组，并打擂台维护当前最大出现次数 current_max。

时间复杂度：\Theta (n\sqrt{n})（常数小）

Code

普通分块（TLE）

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("1,2,3,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falign-loops,-falign-labels,-fdevirtualize,-fcaller-saves,-fcrossjumping,-fthread-jumps,-fwhole-program,-freorder-blocks,-fschedule-insns,inline-functions,-ftree-tail-merge,-fschedule-insns2,-fstrict-aliasing,-fstrict-overflow,-falign-functions,-fcse-skip-blocks,-fcse-follow-jumps,-fsched-interblock,-fpartial-inlining,no-stack-protector,-freorder-functions,-findirect-inlining,-frerun-cse-after-loop,inline-small-functions,-ftree-switch-conversion,-foptimize-sibling-calls,-fexpensive-optimizations,-funsafe-loop-optimizations,inline-functions-called-once,-fdelete-null-pointer-checks")
#pragma G++ optimize("1,2,3,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falign-loops,-falign-labels,-fdevirtualize,-fcaller-saves,-fcrossjumping,-fthread-jumps,-fwhole-program,-freorder-blocks,-fschedule-insns,inline-functions,-ftree-tail-merge,-fschedule-insns2,-fstrict-aliasing,-fstrict-overflow,-falign-functions,-fcse-skip-blocks,-fcse-follow-jumps,-fsched-interblock,-fpartial-inlining,no-stack-protector,-freorder-functions,-findirect-inlining,-frerun-cse-after-loop,inline-small-functions,-ftree-switch-conversion,-foptimize-sibling-calls,-fexpensive-optimizations,-funsafe-loop-optimizations,inline-functions-called-once,-fdelete-null-pointer-checks")

const int N = 1e5 + 5, SN = sqrt(N) + 5;
int n, m, len, a[N], q[SN][N], md[SN][SN], l, r, h[N], rl[N];

inline int ID(int x) { return (x - 1) / len + 1; }

inline int discrete(int (&a)[N], int n) {
    int b[n + 1];
    for (int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b;
    for (int i = 1, x; i <= n; i++) {
        x = lower_bound(b + 1, b + m, a[i]) - b;
        rl[x] = a[i];
        a[i] = x;
    }
    return m;
}

inline int sum(int x, int y, int z) {
    return x <= y ? q[y][z] - q[x - 1][z] : 0;
}

inline int ask(int l, int r) {
    int ret = -1, retsum = -1;
    if (ID(l) == ID(r)) {
        for (int i = l; i <= r; i++) {
            if (++h[a[i]] > retsum || (h[a[i]] == retsum && rl[a[i]] < ret)) {
                ret = rl[a[i]];
                retsum = h[a[i]];
            }
        }
        for (int i = l; i <= r; i++) h[a[i]]--;
        return retsum;
    }
    int bl = ID(l) + 1, br = ID(r) - 1;
    int mode = bl <= br ? md[bl][br] : 0;
    retsum = sum(bl, br, mode);
    ret = mode ? rl[mode] : -1;

    for (int i = l; ID(i) == ID(l); i++) {
        int k = a[i];
        int cnt = sum(bl, br, k) + (++h[k]);
        if (cnt > retsum || (cnt == retsum && rl[k] < ret)) {
            ret = rl[k];
            retsum = cnt;
        }
    }
    for (int i = r; ID(i) == ID(r); i--) {
        int k = a[i];
        int cnt = sum(bl, br, k) + (++h[k]);
        if (cnt > retsum || (cnt == retsum && rl[k] < ret)) {
            ret = rl[k];
            retsum = cnt;
        }
    }
    for (int i = l; ID(i) == ID(l); i++) h[a[i]]--;
    for (int i = r; ID(i) == ID(r); i--) h[a[i]]--;
    return retsum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    len = sqrt(n);

    for (int i = 1; i <= n; i++) cin >> a[i];
    int num = discrete(a, n);

    memset(q[0], 0, sizeof(q[0]));
    for (int i = 1; i <= n; i++) {
        if (ID(i) != ID(i - 1)) memcpy(q[ID(i)], q[ID(i) - 1], sizeof(q[0]));
        q[ID(i)][a[i]]++;
    }

    for (int i = 1; i <= ID(n); i++) {
        for (int j = i; j <= ID(n); j++) {
            if (j == i) {
                int max_cnt = -1, mode = 0;
                for (int k = 1; k <= num; k++) {
                    int cnt = sum(i, j, k);
                    if (cnt > max_cnt || (cnt == max_cnt && k < mode)) {
                        max_cnt = cnt;
                        mode = k;
                    }
                }
                md[i][j] = mode;
            } else {
                md[i][j] = md[i][j - 1];
                int current_max = sum(i, j, md[i][j]);
                for (int k = 1; k <= num; k++) {
                    int cnt = sum(i, j, k);
                    if (cnt > current_max ||
                        (cnt == current_max && k < md[i][j])) {
                        current_max = cnt;
                        md[i][j] = k;
                    }
                }
            }
        }
    }

    while (m--) {
        cin >> l >> r;
        cout << ask(l + 1, r + 1) << '\n';
    }

    return 0;
}

莫队（AC）

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

const int MAXN = 1e5 + 10;

int n, q, block_size;
int a[MAXN], ans[MAXN];
int cnt[MAXN], freq[MAXN], current_max;

struct Query {
    int l, r, idx;
    bool operator<(const Query& other) const {
        if (l / block_size != other.l / block_size)
            return l < other.l;
        else {
            if ((l / block_size) % 2 == 0)
                return r < other.r;
            else
                return r > other.r;
        }
    }
} queries[MAXN];

void add(int x) {
    freq[cnt[x]]--;
    cnt[x]++;
    freq[cnt[x]]++;
    if (cnt[x] > current_max) current_max = cnt[x];
}

void remove(int x) {
    freq[cnt[x]]--;
    cnt[x]--;
    freq[cnt[x]]++;
    if (freq[current_max] == 0) current_max--;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    vector<int> temp(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        temp[i] = a[i];
    }

    // 离散化处理
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    for (int i = 0; i < n; ++i)
        a[i] = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin() + 1;

    // 读取查询
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        queries[i].l = l;
        queries[i].r = r;
        queries[i].idx = i;
    }

    // 设置块大小并排序查询
    block_size = sqrt(n) + 1;
    sort(queries, queries + q);

    // 初始化
    current_max = 0;
    memset(cnt, 0, sizeof(cnt));
    memset(freq, 0, sizeof(freq));
    int cur_l = 0, cur_r = -1;

    for (int i = 0; i < q; ++i) {
        int l = queries[i].l;
        int r = queries[i].r;

        while (cur_l > l) add(a[--cur_l]);
        while (cur_r < r) add(a[++cur_r]);
        while (cur_l < l) remove(a[cur_l++]);
        while (cur_r > r) remove(a[cur_r--]);

        ans[queries[i].idx] = current_max;
    }

    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';

    return 0;
}