题解：P12598 嘟嘟嘟
wukaichen888
·
·
题解
建议降蓝。
考虑莫队。
每次询问 $cnt_i$ 的种数只有 $O(\sqrt n)$。
考虑每次询问怎么快速把 $cnt_i$ 构成的集合找出来。
维护一个队列，每次加删数，如果出现了队列中没有的 $cnt_i$，就加进去，$vis$ 数组记录。
询问时将队列暴力遍历一遍，扔掉实际不存在的 $cnt_i$。
复杂度显然对的。
```cpp
// Problem I
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=4e5+5;
int n,K,q,a[N],bl,br;
int vis[N],q1[N],l1,q2[N],l2;
int cnt[N],cnt2[N],res,ans[N];
struct node{int l,r,id;}b[N];
#define c(x) ((x-1)/K+1)
bool cmp(node x,node y){
if(c(x.r)!=c(y.r)) return x.r<y.r;
if(c(x.r)&1) return x.l<y.l;
return x.l>y.l;
}
inline void add(int x,int y){
x=a[x];
int cx=cnt[x];
cnt2[cx]--;
cnt[x]+=y,cx+=y;
cnt2[cx]++;
if(!vis[cx]) q1[++l1]=cx,vis[cx]=1;
}
int main(){
scanf("%d%d",&n,&q),K=sqrt(n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=q;i++) scanf("%d%d",&b[i].l,&b[i].r),b[i].id=i;
sort(b+1,b+q+1,cmp);
bl=1;
for(int i=1;i<=q;i++){
while(bl>b[i].l) add(--bl,1);
while(br<b[i].r) add(++br,1);
while(bl<b[i].l) add(bl++,-1);
while(br>b[i].r) add(br--,-1);
l2=res=0;
for(int j=1;j<=l1;j++){
vis[q1[j]]=0;
if(cnt2[q1[j]]) q2[++l2]=q1[j];
}
l1=l2;
for(int j=1;j<=l2;j++){
vis[q2[j]]=1;
q1[j]=q2[j],res=max(res,cnt2[q2[j]]*q2[j]);
}
ans[b[i].id]=res;
}
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}
```