zhr 随机跳题跳到的，遂做之。
注意到 \(nk \le 5\times10^5\)，考虑根号分治。
当 \(n\) 很大时，\(k\) 会很小，于是我们记录每一行的前缀和，每一次循环 \(k\) 个数组的前缀和取 \(\max\) 即可，时间复杂度 \(O(qk)\)。
当 \(k\) 很大时，\(n\) 会很小，我们暴力预处理区间 \([l,r]\) 的最大值，直接输出即可，时间复杂度 \(O(n^2k+q)\)。
取阀值为 \(\sqrt n\) 的时候，可以在两边都达到最小值。
点击查看代码
int n,k,q;
vector<int>a[maxn];
vector<int>pre[maxn];
const int lim=750;
int ans[lim+5][lim+5];
signed main() {
in3(n,k,q);
For(i,1,k) {
a[i].push_back(0);
pre[i].push_back(0);
For(j,1,n) {
int x;
in1(x);
a[i].push_back(x);
pre[i].push_back(x+pre[i][j-1]) ;
}
}
if(k<lim) {
For(i,1,q) {
int l,r;
in2(l,r);
int ans=-1e18;
For(j,1,k)
ans=max(ans,pre[j][r]-pre[j][l-1]);
cout<<ans<<'\n';
}
return 0;
}
For(i,1,n) For(j,1,n) ans[i][j]=-1e18;
For(i,1,k) {
For(j,1,n) {
int tot=0;
For(p,j,n) {
tot+=a[i][p];
ans[j][p]=max(ans[j][p],tot);
}
}
}
For(i,1,q) {
int l,r;
in2(l,r);
cout<<ans[l][r]<<'\n';
}
}