自动搬运

查看原文

来自洛谷，原作者为

	wukaichen888 复健 OI

搬运于2025-08-24 23:16:43，当前版本为作者最后更新于2025-05-24 20:51:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

建议降蓝。

考虑莫队。

$cnt_i$ 表示 $a$ 中 $i$ 的出现次数。

每次询问 $cnt_i$ 的种数只有 $O(\sqrt n)$。

考虑每次询问怎么快速把 $cnt_i$ 构成的集合找出来。

维护一个队列，每次加删数，如果出现了队列中没有的 $cnt_i$，就加进去，$vis$ 数组记录。

询问时将队列暴力遍历一遍，扔掉实际不存在的 $cnt_i$。

复杂度显然对的。

// 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;
}