给出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。#includebits/stdc.h using namespace std; typedef long long ll; const int inf0x3f3f3f3f; const ll INFLONG_LONG_MAX; const int N2e57; int res0; 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]?rrhs.r:lrhs.l; } }q[N]; void add(int x) { cnt[num[x]]--; cnt[num[x]1]; num[x]; resmax(res,num[x]); } void del(int x) { if(resnum[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 blocksqrt(n); for(int i1;in;i) { scanf(%d,a[i]); b[i]a[i]; bk[i]i/block; } sort(b1,b1n); int totunique(b1,b1n)-(b1); for(int i1;in;i) a[i]lower_bound(b1,b1tot,a[i])-b; for(int i1;im;i) { scanf(%d%d,q[i].l,q[i].r); q[i].idi; } sort(q1,q1m); int l1,r0; for(int i1;im;i) { while(lq[i].l) l--,add(a[l]); while(rq[i].r) r,add(a[r]); while(lq[i].l) del(a[l]),l; while(rq[i].r) del(a[r]),r--; ans[q[i].id]res; } for(int i1;im;i) printf(%d\n,-ans[i]); return 0; }
