题解 P8572【[JRKSJ R6] Eltaw】
cyffff
·
·
题解
\text{Link}
题意
给你 k 个长为 n 的序列 a_{1\dots k,1\dots n}，有 q 次询问，每次询问给出一个区间 [l,r]，求出所有序列中区间 [l,r] 的和的最大值。
## 思路
暴力题。
先给出做法，对于一次询问的区间 $[l,r]$，如果之前询问过，直接输出之前记录的答案，否则直接 $O(k)$ 求出每个序列的区间和，求最大值并记录即可。
我们来分析复杂度，令 $s=nk$。
考虑到 $n,k$ 中必然有一个小于等于 $\sqrt s$，分类讨论：
1. 当 $n\le k$ 即 $n\le \sqrt s$ 时：
询问的区间只有 $O(n^2)$ 种，每种需要 $O(k)$ 的时间求出，则时间复杂度为 $O(n^2k)$，即为 $O(s\sqrt s)$。
2. 当 $k\le n$ 即 $k\le \sqrt s$ 时：
最坏的情况是每次询问都要 $O(k)$ 回答，此时也只需 $O(qk)$ 即 $O(q\sqrt s)$ 的时间回答。
综上，我们可以在 $O(s\sqrt s+q)$ 或 $O(s+q\sqrt s)$ 的时间内解决本问题。
~~不希望被叫做根号分治。~~
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
}
const int N=5e5+10;
int n,k,q,a[N];
ll pr[N];
map<ll,ll>ans;
int main(){
n=read(),k=read(),q=read();
for(int i=1;i<=k;i++){
int p=(i-1)*n;
for(int j=1;j<=n;j++)
a[++p]=read();
p=(i-1)*n+1;
pr[p]=a[p];
for(int j=2;j<=n;j++)
p++,pr[p]=pr[p-1]+a[p];
}
while(q--){
ll l=read(),r=read();
if(ans.find(l*n+r)!=ans.end()) write(ans[l*n+r]),putc('\n');
else{
ll tmp=0;
for(int i=1;i<=k;i++){
int p=(i-1)*n;
if(l!=1) tmp=max(tmp,pr[p+r]-pr[p+l-1]);
else tmp=max(tmp,pr[p+r]);
}
write(ans[l*n+r]=tmp),putc('\n');
}
}
flush();
}
```
再见 qwq~