P8572 [JRKSJ R6] Eltaw

题目背景

你在月下独自行走，不禁想起了一道简单题。

（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）

题目描述

给你 $k$ 个长为 $n$ 的序列 $a_{1\dots k,1\dots n}$，有 $q$ 次询问，每次询问给出一个区间 $[l,r]$，要求出 $\underset{i=1}{\overset{k}{\max }}\sum _{j=l}^r{a}_{i,j}$，即求出所有序列中区间 $[l,r]$ 的和的最大值。

输入格式

第一行三个整数 $n,k,q$。
接下来 $k$ 行，每行 $n$ 个整数 $a_{i,j}$。
接下来 $q$ 行，每行两个整数 $l,r$ 表示一次询问。

输出格式

输出 $q$ 行表示每个询问的答案。

输入输出样例 #1

输入 #1

7 2 3
1 1 4 5 1 4 0
1 9 1 9 8 1 0
6 7
5 7
1 3

输出 #1

4
9
11

说明/提示

Idea：cyffff，Solution：cyffff，Code：cyffff，Data：cyffff

Eltaw - Fl00t (IN Lv 14.8)

本题输入输出文件较大，请使用恰当的输入输出方式。

数据规模

本题采用捆绑测试。

$\text{Subtask}$	$n\le$	特殊限制	$\text{Score}$
$1$	$5\times 10^3$	$k\le 100$	$20$
$2$	$5\times 10^5$	保证 $l=1$	$30$
$3$	$5\times 10^5$	无	$50$

对于 $100\%$ 的数据，$1\le n,k,q\le 5\times 10^5$，$n\times k\le 5\times 10^5$，$1\le l\le r\le n$，$0\le a_{i,j}\le 10^9$。

数据更新记录

$\text{Upd 2022.10.05}$：更新了两组数据，分别卡掉了两种时间复杂度错误的做法。感谢 @二叉苹果树 指出。

$\text{Upd 2022.10.08}$：更新了一组数据，卡掉了记忆化不正确的做法。感谢 @SweetOrangeOvO 指出。

如果你能通过现在的所有测试点，说明你的代码复杂度极可能是正确的。如果你仍认为你的复杂度是错误的，请联系出题人。

C++实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	register int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
int c[705][705];
signed main(){
	int n=read(),k=read(),q=read();
	int a[k+1][n+1];
	memset(a,0,sizeof(a));
	for(int i=1;i<=k;i++)
		for(int j=1;j<=n;j++){
			int x=read();
			a[i][j]=a[i][j-1]+x;
		}
	if(n<=700){
		for(int i=1;i<=k;i++)
			for(int j=1;j<=n;j++)
				for(int k=1;k<=n;k++)
					c[j][k]=max(c[j][k],a[i][k]-a[i][j-1]);
		while(q--){
			int l=read(),r=read();
			printf("%lld\n",c[l][r]);
		}
		return 0;
	}
	while(q--){
		int l=read(),r=read(),mx=0;
		for(int i=1;i<=k;i++)
			mx=max(mx,a[i][r]-a[i][l-1]);
		printf("%lld\n",mx);
	}
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容