莫队求区间众数 D. Cut and Stick

莫队求区间众数

假设有 (n) 个数，莫队的复杂度是 (n*sqrt(n))

问题：给你一个 (n) 的序列，有 (m) 次询问，每次询问一个区间 ([l,r]) 出现频率最高的数的次数是多少？

复杂度： (n*sqrt(n))

例题：D. Cut and Stick

题目大意：

给你一个序列 (a)，保证： (a_ileq n) ，每次询问一个区间 ([l,r]) ，你可以把这个区间的数分成 (x) 个集合，设 (siz) = 这个集合的大小，要求任意一个集合内相同数的重复次数小于等于 (left lceil frac{siz}{2} ight ceil) ，问最小的 (x) 是多少？

题解：

因为题目难点在于如何求区间出现频率最高的数的次数，所以本篇博客只解决这个问题。

之前写过一篇博客 D. Cut and Stick 线段树 是用线段树的方法解决的，但是这个办法只能求频率大于等于 (left lceil frac{siz}{2} ight ceil) 的次数，是有一个先决条件的。

接下来讲的方法是没有任何条件的，只需要复杂度满足即可。

维护众数的出现次数：用 (cnt[i]) 维护数字i的出现次数，用 (num[i]) 维护出现了 (i) 次的数字有多少个，因此，最大的不为 0 的 (num[]) 的下标即为众数的出现次数。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
typedef long long ll;
int a[maxn], pos[maxn] ,vis[maxn],ans[maxn];
struct node{
    int l, r, id;
}ex[maxn];
bool cmp(node a,node b){
    return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
}
/*
 * 维护众数的出现次数：用cnt[i]维护数字i的出现次数，用num[i]维护出现了i次的数字有多少个，因此，最大的不为0的num[]的下标即为众数的出现次数。
 */
int cnt[maxn],num[maxn],Ans;
void add(int x) {
    --num[cnt[a[x]]], ++num[++cnt[a[x]]];
    while (num[Ans + 1]) ++Ans;
}

void del(int x) {
    --num[cnt[a[x]]],++num[--cnt[a[x]]];
    while (!num[Ans]) --Ans;
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    int siz = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pos[i] = i / siz;
    }
    for (int i = 1; i <= q; i++) {
        scanf("%d%d", &ex[i].l, &ex[i].r);
        ex[i].id = i;
    }
    sort(ex + 1, ex + 1 + q, cmp);
    Ans = 0,num[0] = 1;
    int l = 1, r = 0;
    for (int i = 1; i <= q; i++) {
        int ql = ex[i].l, qr = ex[i].r;
        while (r < qr) add(++r);
        while (r > qr) del(r--);
        while (l < ql) del(l++);
        while (l > ql) add(--l);
        ans[ex[i].id] = 2 * Ans - (qr - ql + 1);
    }
    for (int i = 1; i <= q; i++) {
        printf("%d
", max(1, ans[i]));
    }
    return 0;
}