前缀和思想 [USACO17DEC]Haybale Feast G（洛谷 P4085）

[USACO17DEC]Haybale Feast G

题目大意：

给你两个数列F和S，求所有满足 ∑ k = i j F k \sum_{k=i}^{j} F_k ∑k=ij​Fk​ >= M的（i，j）；

在这些（i，j）中求max( S i S_i Si​, S i + 1 , . . . , S j − 1 , S j S_{i+1},...,S_{j-1},S_j Si+1​,...,Sj−1​,Sj​)的最小值；

首先会想到n^2的暴力，先预处理出F数列的前缀和，然后枚举 i （1到n），枚举 j （n到1），找到所有（i，j），然后线段树维护S数列的区间（i，j）最大值即可；这显然过不了；

因为题目保证 F i F_i Fi​ 是大于1的，所以可以想到当 i 等于1时，找到 j 1 j_1 j1​ ，当 i 等于2时，j 是不是只要从 j 1 j_1 j1​后面开始找就行了；

还有个区间最大值最小问题，当求到（i，j）的最大值mx时，j 后面的元素要不就比mx大，要不就比mx小；

如果比mx大，那么区间最大值就不是mx，但是最后是求最大值最小；

如果比mx小，那么就区间最大值就是mx；

所以最后只要求（i，j）的最大值即可；

代码：

#include<bits/stdc++.h>
#define LL long long
#define pa pair<int,int>
#define ls k<<1
#define rs k<<1|1
#define inf 0x3f3f3f3f
using namespace std;
const int N=100100;
const int M=50100;
const LL mod=10007;
struct Node{
	int l,r;
	LL mx;
}tr[N*4];
int n;
LL m,f[N],s[N],sum[N];
void build(int l,int r,int k){
	tr[k].l=l,tr[k].r=r;
	if(l==r){
		tr[k].mx=s[l];
		return;
	}
	int d=(l+r)>>1;
	build(l,d,ls);
	build(d+1,r,rs);
	tr[k].mx=max(tr[ls].mx,tr[rs].mx);
}
LL query(int l,int r,int k){
	if(tr[k].l>=l&&tr[k].r<=r) return tr[k].mx;
	int d=(tr[k].l+tr[k].r)>>1;
	LL mmax=0;
	if(l<=d) mmax=max(mmax,query(l,r,ls));
	if(r>d) mmax=max(mmax,query(l,r,rs));
	return mmax;
}
int main(){
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&f[i],&s[i]),sum[i]=sum[i-1]+f[i];
	build(1,n,1);
	int j=1;
	LL ans=2e9;
	for(int i=1;i<=n;i++){
		for(;j<=n;j++) if(sum[j]-sum[i-1]>=m) break;
		if(sum[j]-sum[i-1]<m) break;
		ans=min(ans,query(i,j,1));
	}
	printf("%lld\n",ans);
	return 0;
}