P3709 大爷的字符串题 (莫队)

题目

p3709 大爷的字符串题
题意：求\([l,r]\)中众数的个数。

解析

维护两个数组：

• \(cnt[x]\)，数\(x\)出现的次数。
• \(sum[x]\)，出现次数为\(x\)的数的个数。

考虑往里添加元素时，直接取\(max\)；
删除元素时，如果这个数是众数(\(cnt[x]==mode\))且众数只有这一个数(\(sum[cnt[x]]==1\))，众数个数就减一；

代码

#include <bits/stdc++.h>
using namespace std;
const int n = 1e7 + 10;
int n, m, mode;
int a[n], b[n], cnt[n], sum[n], ans[n];
class node {
    public :
        int l, r, id, bl;
        bool operator < (const node &oth) const {
            return this->bl == oth.bl ? this->r < oth.r : this->l < oth.l;
        }
} e[n];

template<class t>inline void read(t &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x;
    return;
}

inline void add(int x) {
    sum[cnt[a[x]]]--, sum[++cnt[a[x]]]++, mode = max(mode, cnt[a[x]]);
    //前两句是维护sum这个数出现的次数。
}

inline void del(int x) {
    if (cnt[a[x]] == mode && sum[cnt[a[x]]] == 1) mode--;
    sum[cnt[a[x]]]--;
    sum[--cnt[a[x]]]++;
}

int main() {
    read(n), read(m);
    int k = sqrt(n);
    for (int i = 1; i <= n; ++i) read(a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n);
    int len = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
    for (int i = 1, x, y; i <= m; ++i) {
        read(x), read(y);
        e[i] = (node) {x, y, i, x / k + 1};
    }
    sort(e + 1, e + 1 + m);
    int l = 1, r = 0;
    for (int i = 1; i <= m; ++i) {
        int ll = e[i].l, rr = e[i].r;
        while (l < ll) del(l++);
        while (l > ll) add(--l);
        while (r < rr) add(++r);
        while (r > rr) del(r--);
        ans[e[i].id] = mode; 
    }
    for (int i = 1; i <= m; ++i) printf("%d\n", -ans[i]);
    return 0;
}