LightOJ 1339 Strongest Community：莫隊算法（分塊暴力）解決區間眾數頻率

題目背景

直線上有 n 棟房子，屬於 c 個連續區段組成的社區。q 次詢問：區間 [i, j] 中出現次數最多的社區編號出現了多少次？n ≤ 1e5, q ≤ 5e4，數據量大需快速 I/O。

莫隊算法核心思想

離線處理所有詢問，將查詢按左端點所在塊排序，塊內按右端點排序。維護雙指針 [L, R] 表示當前區間，單步擴展/收縮時更新統計信息，時間復雜度 O((n+q)√n)。

關鍵統計結構設計

• num[v]：值 v 在當前區間的出現次數
• h[c]：出現次數恰好為 c 的值的個數
• sum：當前區間的最大出現次數（即答案）

Add / Sub 操作

void Add(int x) {
    int val = a[x];
    h[num[val]]--;
    num[val]++;
    h[num[val]]++;
    if (num[val] > sum) sum = num[val];
}

void Sub(int x) {
    int val = a[x];
    h[num[val]]--;
    num[val]--;
    h[num[val]]++;
    if (sum == num[val] + 1 && !h[num[val] + 1]) sum = num[val];
}

完整 AC 代碼

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define REPF(i,a,b) for(int i=a;i<=b;++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define CLEAR(a,x) memset(a,x,sizeof(a))
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 100;

int pos[maxn], a[maxn], h[maxn], num[maxn], ans[maxn];
struct Query { int l, r, id; } q[maxn];
int t, n, c, m, block, sum;

int cmp(Query a, Query b) {
    if (pos[a.l] == pos[b.l]) return a.r < b.r;
    return pos[a.l] < pos[b.l];
}

int main() {
    int x, y, cas = 1;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &c, &m);
        CLEAR(h, 0); CLEAR(num, 0);
        block = sqrt(n * 1.0 + 0.5);
        REPF(i, 1, n) {
            scanf("%d", &a[i]);
            pos[i] = (i - 1) / block + 1;
        }
        REP(i, m) {
            scanf("%d%d", &x, &y);
            q[i] = {x, y, i};
        }
        sort(q, q + m, cmp);
        sum = 0; int L = 1, R = 0;
        printf("Case %d:\n", cas++);
        REP(i, m) {
            int l = q[i].l, r = q[i].r;
            while (L > l) Add(--L);
            while (R < r) Add(++R);
            while (L < l) Sub(L++);
            while (R > r) Sub(R--);
            ans[q[i].id] = sum;
        }
        REP(i, m) printf("%d\n", ans[i]);
    }
    return 0;
}