faebdc的烦恼 莫队
思路
有点难想的莫队。
首先我们肯定要一个cnt[i]记录难度i出现的次数，但是我们发现每次删去一个难度后，如果那个难度的个数恰好是当前最多次数，我们就可能要更新一下答案，而这取决于有多少难度的个数恰好是当前最多次数，于是我们再开一个sum[i]记录有多少难度的个数为i。
经过上述分析容易得到莫队更新规则：
inline void add(int x){
--sum[cnt[a[x]]];
++cnt[a[x]];
++sum[cnt[a[x]]];
ans=max(cnt[a[x]], ans);
}
inline void del(int x){
--sum[cnt[a[x]]];
if(cnt[a[x]]==ans&&sum[cnt[a[x]]]==0) --ans;
--cnt[a[x]];
++sum[cnt[a[x]]];
}
另外注意一下因为范围为(-10^5le a[i]le 10^5)，所以我们可以将所有数先加上(10^5)
例码
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 100010
#define MAXQ 200010
using namespace std;
int ans,cnt[100001*2],sum[100001];
int a[MAXN];
inline void add(int x){
--sum[cnt[a[x]]];
++cnt[a[x]];
++sum[cnt[a[x]]];
ans=max(cnt[a[x]], ans);
}
inline void del(int x){
--sum[cnt[a[x]]];
if(cnt[a[x]]==ans&&sum[cnt[a[x]]]==0) --ans;
--cnt[a[x]];
++sum[cnt[a[x]]];
}
struct nod{
int l,r,bid,qid;
} q[MAXQ];
bool cmp(const nod &a, const nod &b){
return (a.bid^b.bid?(a.l<b.l):((a.bid&1)?(a.r<b.r):(a.r>b.r)));
}
int n,m,blo,res[MAXQ];
int main()
{
scanf("%d %d", &n, &m);
blo=n/sqrt(m*2/3);
for(int i=1;i<=n;++i) scanf("%d", &a[i]),a[i]+=100000;
for(int i=1;i<=m;++i){
scanf("%d %d", &q[i].l, &q[i].r);
q[i].bid=q[i].l/blo;
q[i].qid=i;
}
sort(q+1, q+1+m, cmp);
int l=1,r=1;cnt[a[1]]=1;sum[1]=1;ans=1;
for(int i=1;i<=m;++i){
while(l<q[i].l) del(l++);
while(l>q[i].l) add(--l);
while(r>q[i].r) del(r--);
while(r<q[i].r) add(++r);
res[q[i].qid]=ans;
}
for(int i=1;i<=m;++i) printf("%d
", res[i]);
return 0;
}
2019.10 update 才发现这次国庆集训Day1 老师不就是faebdc吗？！