萌新求助回滚莫队
查看原帖
萌新求助回滚莫队
560155
通行禁止楼主2021/11/5 19:27

RT,样例全过,但是保龄,有没有大佬知道可能是出了什么问题

#include<bits/stdc++.h>
using namespace std;
struct ZS{
	int x,y;
	int block,id;
	bool operator <(const ZS b)const{return block<b.block||(block==b.block&&y<b.y);}
}q[100005];
int n,m,len,L,R;
int maxn[2];
int a[100005],s[100005],ed[1000005];
long long ans[100005];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
void del(int x){s[a[x]]--;}
void add(int x,int opt){if((long long)a[maxn[opt]]*s[a[maxn[opt]]]<(long long)a[x]*(++s[a[x]]))maxn[opt]=x;}
int main(){
	n=read();m=read();len=sqrt(n);
	for(int i=1;i<=n;i++)a[i]=read();ed[n]=n;
	for(int i=n-1;i>=1;i--)if((i-1)%len)ed[i]=i;else ed[i]=ed[i+1];
	for(int i=1;i<=m;i++){q[i].x=read();q[i].y=read();q[i].id=i;q[i].block=(q[i].x-1)/len+1;}
	sort(q+1,q+1+m);
	for(int i=1;i<=m;i++){
		if(q[i].block!=q[i-1].block){L=q[i].x;R=q[i].x-1;memset(s,0,sizeof s);maxn[1]=0;}
		maxn[0]=0;
		while(L<=min(ed[q[i-1].x],R))del(L++);
		while(R<q[i].y)add(++R,1);
		while(q[i].x<L)add(--L,0);
		ans[q[i].id]=max((long long)a[maxn[0]]*s[a[maxn[0]]],(long long)a[maxn[1]]*s[a[maxn[1]]]);
	}
	for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return 0;
}
2021/11/5 19:27
加载中...