P3709 大爷的字符串题

题意

询问区间众数出现的次数

思路

唯有水题快人心
离散化+莫队
莫队一定要先加后减，有事会出错的
莫队维护区间众数:
维护两个数组，一个数组记录权值为x的出现次数，一个记录出现次数为x的数的个数
add很简单，更新ans
delete的时候，删除的是ans话，查看出现次数为x的个数是否为1，是就ans--(这里删除后至少为ans--)，不是就和ans无关

代码

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=200007;
int a[maxn],b[maxn],n,m;
int ans,belong[maxn],vis[maxn],num[maxn];
struct node {
    int s,t,id;
    int ans;
    bool operator < (const node &b) const {
        return belong[s]==belong[b.s] ? t<b.t : s<b.s ;
    }
}Q[maxn];
bool cmp(node a,node b)
{
    return a.id<b.id;
}
void add(int x)
{
    num[vis[x]]--;
    vis[x]++;
    if(ans<vis[x]) ans++;
    num[vis[x]]++;
}
void delet(int x)
{
    if(ans==vis[x] && num[vis[x]]==1) ans--;
    num[vis[x]]--;
    vis[x]--;
    num[vis[x]]++;
}
int main()
{
    scanf("%d%d",&n,&m);
    int k=sqrt(n);
    FOR(i,1,n) scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    FOR(i,1,n)  a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    FOR(i,1,n) belong[i]=(i-1)/k+1;
    FOR(i,1,m) scanf("%d%d",&Q[i].s,&Q[i].t),Q[i].id=i;
    sort(Q+1,Q+1+m);
    int l=1,r=0;
    FOR(i,1,m)
    {
        while(l > Q[i].s) add(a[--l]);
        while(l < Q[i].s) delet(a[l++]);
        while(r < Q[i].t) add(a[++r]);
        while(r > Q[i].t) delet(a[r--]);
        Q[i].ans=max(ans,0);
    }
    sort(Q+1,Q+1+m,cmp);
    FOR(i,1,m) printf("%d\n",-Q[i].ans);
    return 0;
}