P8572 题解
Jerrlee✅
2022-10-04 20:14:01
这次比赛蛮不错的，赛时好好写了几题，$310$ 分跑路（
## 题意
给你 $k$ 个长为 $n$ 的序列 $a_{1\dots k,1\dots n}$，$q$ 次询问，每次询问求 $k$ 个序列中区间 $[l,r]$ 的和的最大值。
## 思路
求区间最大值，一眼可以想到前缀和。~~对就是用眼睛想（雾~~
但是按照题意写完后，你会发现你只有 [$20$ 分](https://www.luogu.com.cn/record/88543516)。
观察数据范围，发现 $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 了这题。
具体见代码，应该还是比较好懂的。
~~甭管他叫不叫根号分治，反正思想有点像，但主要是复杂度分析~~。
## 代码
```cpp
#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 记录](https://www.luogu.com.cn/record/88577357)