洛谷P3709 大爷的字符串题 莫队

给出nnn个数，以及mmm个询问，每次询问一个区间里面众数的次数。值域范围不超过1e91e91e9。
由于只有nnn个数，考虑对所有的数离散化。然后莫队对区间排序。记录每个数出现的次数num[x]num[x]num[x]，同时也记录下出现次数为xxx的数总共有cnt[x]cnt[x]cnt[x]个。增加的时候直接用num[x]num[x]num[x]暴力更新，删除的时候判定一下条件，如果num[x]num[x]num[x]为当前答案，并且cnt[num[x]]==1cnt[num[x]]==1cnt[num[x]]==1，那么原答案−1-1−1。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const ll INF=LONG_LONG_MAX; const int N=2e5+7; int res=0; int a[N],b[N],bk[N]; int ans[N]; int num[N]; // 每个数出现次数 int cnt[N]; // 出现次数i多少个 struct Query { int l,r,id; bool operator <(const Query &rhs) const { return bk[l]==bk[rhs.l]?r<rhs.r:l<rhs.l; } }q[N]; void add(int x) { cnt[num[x]]--; cnt[num[x]+1]++; num[x]++; res=max(res,num[x]); } void del(int x) { if(res==num[x]&&cnt[num[x]]==1) res--; cnt[num[x]]--; cnt[num[x]-1]++; num[x]--; } int main() { int n,m; scanf("%d%d",&n,&m); int block=sqrt(n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; bk[i]=i/block; } sort(b+1,b+1+n); int tot=unique(b+1,b+1+n)-(b+1); for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+tot,a[i])-b; for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+1+m); int l=1,r=0; for(int i=1;i<=m;i++) { while(l>q[i].l) l--,add(a[l]); while(r<q[i].r) r++,add(a[r]); while(l<q[i].l) del(a[l]),l++; while(r>q[i].r) del(a[r]),r--; ans[q[i].id]=res; } for(int i=1;i<=m;i++) printf("%d\n",-ans[i]); return 0; }