Jerrlee's blog

Jerrlee's blog

(2Y /-\|< |0|!

P8572 题解

posted on 2022-10-04 20:14:01 | under 题解 |

这次比赛蛮不错的,赛时好好写了几题,$310$ 分跑路(

题意

给你 $k$ 个长为 $n$ 的序列 $a_{1\dots k,1\dots n}$,$q$ 次询问,每次询问求 $k$ 个序列中区间 $[l,r]$ 的和的最大值。

思路

求区间最大值,一眼可以想到前缀和。对就是用眼睛想(雾

但是按照题意写完后,你会发现你只有 $20$ 分

观察数据范围,发现 $n \times k$ 小于 $5 \times 10^5$,但是 $q \times k$ 并不满足,所以 $O(q \times k)$ 的询问复杂度是过不去的。

有个小提示:

$4\times 10^8$ 次运算可以在 $2$ 秒内完成。

已知 $5 \times 10^5 \times \sqrt{5 \times 10^5} \approx 3.5 \times 10^8$,说明复杂度可能含有根号。

如果预处理每次询问,可以在 $O(n^2 \times k)$ 的复杂度跑完(预处理 $O(n^2 \times k)$,回答询问 $O(1)$),而 $n \leq \sqrt{5 \times 10^5}$ 的情况下,你可以轻松(?)过去。

再加上前文 $O(q \times k)$ 的询问复杂度,两种情况分类一下,你就 AC 了这题。

具体见代码,应该还是比较好懂的。

甭管他叫不叫根号分治,反正思想有点像,但主要是复杂度分析

代码

#define int long long//__int128
int jrl[500009];
signed main(){
    int n,k,q;
    cin>>n>>k>>q;
    int a[k+1][n+1];
    int qzh[k+9][n+9];
    int Jerrlee=sqrt(500000);
    int ans[Jerrlee+9][Jerrlee+9];//这边要注意,数组开大会 MLE
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            qzh[i][j]=qzh[i][j-1]+a[i][j];//前缀和
        }
    }
    for(int i=1;i<=k;i++)
        for(int j=1;j<=n;j++)
            jrl[j]=max(jrl[j],qzh[i][j]);//这段是专为 sub2 写的,同时能有效缩短一内内时间,但是不加也能过
    if(k>sqrt(500000)){
    memset(ans,0,sizeof ans);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            for(int z=1;z<=k;z++)
                ans[i][j]=max(ans[i][j],qzh[z][j]-qzh[z][i-1]);//这是前文所说第二种方法的预处理
    }//O(n^2 k)
    while(q--){
        int x,y;
        cin>>x>>y;
        if(x==1){cout<<jrl[y]-jrl[x-1]<<endl;continue;}//O(n k) in total
        int cnt=LLONG_MIN;
        if(k>sqrt(500000)){
            cout<<ans[x][y]<<endl;
        }//O(1)
        else{
            for(int i=1;i<=k;i++) cnt=max(cnt,qzh[i][y]-qzh[i][x-1]);
            cout<<cnt<<endl;
        }//O(q k)
    }
}

AC 记录