自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:40:16，当前版本为作者最后更新于2022-05-30 13:17:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{Link}$

题意

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

$1\le n,k,q\le5\times 10^5$，$1\le n\times k\le 5\times10^5$。

思路

暴力题。

先给出做法，对于一次询问的区间 $[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)$ 的时间内解决本问题。

不希望被叫做根号分治。

代码：

#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~