传送门
Description
IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件。
日记中记录了连续N天发生的时间,大约每天发生一件。
事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示,Xi越大,事件的规模就越大。
JOI教授决定用如下的方法分析这些日记:
选择日记中连续的一些天作为分析的时间段
事件种类t的重要度为t*(这段时间内重要度为t的事件数)
计算出所有事件种类的重要度,输出其中的最大值
现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。
Solution
回滚莫队。。。
有些时候,增加操作是不可逆的,就比如说求最值什么的
对于左端点所在的块相同的询问,它们右端点单增
而左边,你只需要让left停留在这个块的最右边
每次暴力往左推,但不更新ans,这样就可以避免删除了
Code
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
#define MN 100005
int n,m,T,a[MN],R[1005];
struct ques{
int l,r,pl,pr,id;
bool operator <(const ques &o) const {return (pl^o.pl)?(pl<o.pl):(r<o.r);}
}q[MN];
int num[MN],tot,fnum[MN],num2[MN];
ll Ans[MN];
int main()
{
n=read();m=read();T=sqrt(n);
register int i,j,l=1,r=0;register ll ans;
for(i=0;i<=n;i+=T) R[i/T+1]=min(i+T,n);
for(i=1;i<=n;++i) a[i]=read(),fnum[i]=a[i];
std::sort(fnum+1,fnum+n+1);
tot=std::unique(fnum+1,fnum+n+1)-fnum-1;
for(i=1;i<=n;++i) a[i]=std::lower_bound(fnum+1,fnum+tot+1,a[i])-fnum;
for(i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].pl=(q[i].l-1)/T+1,q[i].pr=(q[i].r-1)/T+1,q[i].id=i;
std::sort(q+1,q+m+1);
for(i=1;i<=m;++i)
{
if(q[i].pl^q[i-1].pl) memset(num,0,sizeof num),l=R[q[i].pl]+1,r=R[q[i].pl],ans=0ll;
if(q[i].pl==q[i].pr)
{
register ll tmp=0ll;
for(j=q[i].l;j<=q[i].r;++j) num2[a[j]]=0;
for(j=q[i].l;j<=q[i].r;++j) tmp<1ll*(++num2[a[j]])*fnum[a[j]]?tmp=1ll*num2[a[j]]*fnum[a[j]]:0;
Ans[q[i].id]=tmp;
}
else
{
for(;r<q[i].r;++r) ans<1ll*(++num[a[r+1]])*fnum[a[r+1]]?ans=1ll*num[a[r+1]]*fnum[a[r+1]]:0;
register ll tmp=ans;
for(;l>q[i].l;--l) tmp<1ll*(++num[a[l-1]])*fnum[a[l-1]]?tmp=1ll*num[a[l-1]]*fnum[a[l-1]]:0;
for(;l<R[q[i].pl]+1;++l) --num[a[l]];
Ans[q[i].id]=tmp;
}
}
for(i=1;i<=m;++i) printf("%lld\n",Ans[i]);
return 0;
}
Blog来自PaperCloud,未经允许,请勿转载,TKS!