牛客竞赛 NC15553 数学考试

---

传送门 $\looparrowright$

题目描述

今天 $\text{qwb}$ 要参加一个数学考试，这套试卷一共有 $n$ 道题，每道题 $\text{qwb}$ 能获得的分数为 $a_i$，$\text{qwb}$ 并不打算把这些题全做完，他想选总共 $2k$ 道题来做，并且期望他能获得的分数尽可能的大，他准备选 $2$ 个不连续的长度为 $k$ 的区间，即 $[L,L+1,L+2,....,L+k-1]$，$[R,R+1,R+2,...,R+k-1]$$(R \geqslant L+k)$ 。

输入描述

第一行一个整数 $T$$(T\leqslant 10)$,代表有 $T$ 组数据。
接下来一行两个整数 $n,k$$(1\leqslant n\leqslant 200000)$$(1\leqslant k,2k \leqslant n)$。
接下来一行 $n$ 个整数 $a_1,a_2,...,a_n$$(-100,000\leqslant a_i\leqslant 100000)$。

输出描述

输出一个整数，$\text{qwb}$ 能获得的最大分数。

示例1

输入
2
6 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1
输出
6
7

分析

定义 $sum[i]=\sum\limits_{j=i}^{i+k-1} a[j]$ ，每次枚举 $L$ 得 $sum[L]$，然后查询区间 $[L+k,n]$ 内长度为 $k$ 的区间最大值，即查询 $\max\limits_{L+k\leqslant i\leqslant n-k+1} sum[i]$，这显然是一个简单的 $\text{RMQ}$ 问题，可用 $\text{ST}$ 表维护 $sum[i]$ 的区间最大值。$sum[L]+\max\limits_{L+k\leqslant i\leqslant n-k+1} sum[i]$ 有可能成为答案，$O(n)$ 枚举 $L$，即可得到答案。

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#define N 200003
#define ll long long
using namespace std;
int a[N];
ll sum[N];
int _log2[N];
ll f[N][18];//ST表
int n,k;
int nn;
/*预处理以2为底的对数值（向下取整）*/
void pre()
{
	_log2[1]=0;
	int i;
	for(i=2;i<N;i++) _log2[i]=_log2[i>>1]+1;
}
/*-------ST表初始化------*/
void init()
{
	int i,j;
	for(i=1;i<=nn;i++) f[i][0]=sum[i];//边界值
	for(j=1;(1<<j)<=nn;j++)
	{
		for(i=1;i+(1<<j)-1<=nn;i++)
		{
			f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
}
int main()
{
	int _;
	pre();
	for(cin>>_;_;_--)
	{
		scanf("%d%d",&n,&k);
		int i;
		for(i=1;i<=n;i++) scanf("%d",a+i);
		nn=n-k+1;
		ll temp=0;
		/*===========================*/
		for(i=1;i<=n;i++)//计算sum[i]
		{
			if(i<=k) temp+=a[i];
			else
			{
				sum[i-k]=temp;
				temp=temp-a[i-k]+a[i];
			}
		}
		sum[nn]=temp;
		/*===========================*/
		init();//处理ST表
		ll ans=-1000000000000000000;
		for(i=1;i<=n-2*k+1;i++)//枚举第一个区间
		{
			int l=i+k,r=nn;
			int s=_log2[r-l+1];
			//查询区间[i+k,nn]内最大的sum[i]
			ans=max(ans,sum[i]+max(f[l][s],f[r-(1<<s)+1][s]));
		}
		printf("%lld\n",ans);
	}
	return 0;
}