AT1219 歴史の研究 解题报告

AT1219 歴史の研究

题意

给定一个长为\(n\)的序列\(\{a\}\)，询问区间\(a*cnt_a\)的最大值，即某个值乘上出现次数

---

回退莫队板子

只右移右指针和左指针每次回到块结尾即可。

---

Code:

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#define ll long long

const int N=1e5+10;

using std::max;

using std::min;

int n,q,yuy[N],a[N],bee[N];

struct node

{

	int l,r,lp,id;

	node(){}

	node(int l,int r,int lp,int id){this->l=l,this->r=r,this->lp=lp,this->id=id;}

	bool friend operator <(node a,node b){return a.lp==b.lp?a.r<b.r:a.lp<b.lp;}

}dew[N];

ll ans,tans,Ans[N];

void add(int p)

{

	++bee[a[p]];

	ans=max(ans,1ll*bee[a[p]]*yuy[a[p]]);

}

int main()

{

	scanf("%d%d",&n,&q);

	for(int i=1;i<=n;i++) scanf("%d",a+i),yuy[i]=a[i];

	std::sort(yuy+1,yuy+1+n);

	int m=std::unique(yuy+1,yuy+1+n)-yuy-1;

	for(int i=1;i<=n;i++) a[i]=std::lower_bound(yuy+1,yuy+1+m,a[i])-yuy;

	int B=sqrt(n)+1,qn=0;

	for(int l,r,i=1;i<=q;i++)

	{

		scanf("%d%d",&l,&r);

		if(r-l<=B)

		{

			ans=0;

			for(int j=l;j<=r;j++)

			{

				++bee[a[j]];

				ans=max(ans,1ll*bee[a[j]]*yuy[a[j]]);

			}

			Ans[i]=ans;

			for(int j=l;j<=r;j++)

				bee[a[j]]=0;

		}

		else

			dew[++qn]=node(l,r,(l-1)/B+1,i);

	}

	std::sort(dew+1,dew+1+qn);

	for(int l,r,bcnt=0,i=1;i<=qn;i++)

	{

		if(dew[i].lp!=bcnt)

		{

			bcnt=dew[i].lp;

			ans=0;

			memset(bee,0,sizeof bee);

			l=min(dew[i].lp*B,n)+1,r=l-1;

		}

		while(r<dew[i].r) add(++r);

		tans=ans;

		while(l>dew[i].l) add(--l);

		Ans[dew[i].id]=ans;

		int tl=l;

		ans=tans,l=min(dew[i].lp*B,n)+1;

        for(int j=tl;j<l;j++) --bee[a[j]];

	}

	for(int i=1;i<=q;i++) printf("%lld\n",Ans[i]);

	return 0;

}

---

2019.1.28