在固定左端点,枚举右端点倍增时,
以下代码会T掉4个点:
for(int i=1;i<=n;++i)
{
for(int j=i;j<=n;++j)
{
ll res=findx(1,1,n,i,j);
for(int k=lg[n]+1;k>=0;--k)
{
if(j+(1<<k)<=n&&findx(1,1,n,i,j+(1<<k))==res)j+=(1<<k);
}
ans=max(ans,(j-i+1)*res);
}
}
但如果将第三层循环中的循环范围缩小到 log2(n−j) 就能过。
for(int i=1;i<=n;++i)
{
for(int j=i;j<=n;++j)
{
ll res=findx(1,1,n,i,j);
for(int k=lg[n-j]+1;k>=0;--k)
{
if(j+(1<<k)<=n&&findx(1,1,n,i,j+(1<<k))==res)j+=(1<<k);
}
ans=max(ans,(j-i+1)*res);
}
}