警示后人
查看原帖
警示后人
353893
彭俊皓123楼主2023/7/25 14:58

在固定左端点,枚举右端点倍增时,

以下代码会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)log_2(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);
        }
    }
2023/7/25 14:58
加载中...