题解 P1997 【faebdc 的烦恼】

Strelitzia · 2020-09-04 21:50:56 · 题解

题目传送门

题目要求你求区间的众数，很明显可以用莫队。

维护一个 \operatorname {cnt} 来记录出现的次数，\operatorname {sum} 来维护（出现次数）出现的次数。

注意 a_i 有负数，可以统一加上一个值。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

template<typename T>void read(T &x) {
    T f = 1;x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}
    while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}
    x *= f;
}
template<typename T>void print(T x) {
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

const int maxn = 200005;

int n,m,res,a[maxn],b[maxn],pos[maxn],cnt[maxn],ans[maxn],sum[maxn];

struct node {
    int l,r,id;
    bool operator <(node y) const {
        return pos[this->l] ^ pos[y.l] ? this->l < y.l : (pos[this->l] & 1 ? this->r < y.r : this->r > y.r);
    }
}ask[maxn];

bool cmp(int x,int y) {
    return a[x] < a[y];
}

void Add(int x) {
    sum[cnt[x]] --;
    sum[++ cnt[x]] ++;
    res = max(cnt[x],res);
}

void Sub(int x) {
    if (cnt[x] == res && sum[cnt[x]] == 1) res --;
    sum[cnt[x]] --;
    sum[-- cnt[x]] ++;
}

int main () {
    read(n);read(m);
    int t = sqrt(n);
    for (int i = 1 ; i <= n ; ++ i) {
        read(a[i]);pos[i] = i / t;
        a[i] += 1e5;
    }
    for (int i = 1 ; i <= m ; ++ i) {
        read(ask[i].l);read(ask[i].r);
        ask[i].id = i;
    }
    sort(ask + 1,ask + 1 + m);
    int l = 1,r = 0;
    for (int i = 1 ; i <= m ; ++ i) {
        while (l > ask[i].l) Add(a[-- l]);
        while (r < ask[i].r) Add(a[++ r]);
        while (l < ask[i].l) Sub(a[l ++]);
        while (r > ask[i].r) Sub(a[r --]);
        ans[ask[i].id] = res;
    }
    for (int i = 1 ; i <= m ; ++ i) print(ans[i]),putchar('\n');
    return 0;
}