自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:08:37，当前版本为作者最后更新于2025-02-14 21:53:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Problem Link

题目大意

给定 $a_1\sim a_n,b_1\sim b_{n-1}$，每个 $b_i$ 可以选择 $x\in[0,b_i]$，给 $a_i$ 加上 $x$，$a_{i+1}$ 加上 $b_i-x$。

$q$ 次询问 $[l,r]$，求 $\min a[l,r]$ 的最大值。

数据范围：$n,q\le 10^5$。

思路分析

首先二分答案 $k$，然后可以看成一个二分图匹配问题，左部点是 $l\sim r$，右部点是所有 $a,b$。

用 Hall 定理判定，显然只要考虑左部点集是一个区间的情况，即对每个子区间 $[x,y]$ 要求 $k(y-x+1)\ge b_{x-1}+\sum_{i=x}^y a_i+b_i$。

那么答案就是所有子区间 $[x,y]$ 对应的 $\left\lfloor\dfrac{A_y+B_y-A_{x-1}-B_{x-2}}{y-x+1}\right\rfloor$ 的最小值，其中 $A,B$ 是 $a,b$ 的前缀和。

稍加转化变成求区间中最小的 $\dfrac{R_y-L_x}{y-x}$，其中 $l-1\le x<y\le r$。

看成求 $(y,R_y)$ 到所有 $(x,L_x)$ 的最小斜率，那么动态维护 $(x,L_x)$ 构成的凸壳，查询时二分就能求出每个前缀的答案。

对于一般的情况可以分块，隔 $\sqrt n$ 放一个关键点，然后维护每个关键点的所有前缀和所有后缀的答案。

此时一个查询只剩下 $x,y$ 都在散块的点对贡献未考虑，这种直接暴力加入这 $\mathcal O(\sqrt n)$ 个散块元素，还是用刚才的结构维护答案即可。

时间复杂度 $\mathcal O(\sqrt n\log n)$，瓶颈在二分凸壳上的切点。

我们尝试优化掉二分，用单调队列维护切点。

这个做法的正确性依赖于决策单调性，即每个点的最优转移点递增。

假设 $x_2<x_1<y_1<y_2$，且 $y_1$ 的决策点在 $x_1$，$y_2$ 的决策点在 $x_2$。

首先 $f(x_1,y_1)>f(x_2,y_1)$，说明 $[x_2,x_1)$ 范围内的平均数 $>$ $[x_1,y_1]$ 范围内的平均数。

同理 $f(x_1,y_2)<f(x_2,y_2)$，说明 $[x_2,x_1)$ 范围内的平均数 $<$ $[x_1,y_2]$ 范围内的平均数。

那么 $[x_1,y_1]$ 范围内的平均数 $<$ $[x_1,y_2]$ 范围内的平均数，因此这种情况下 $f(x,y_2)>f(x,y_1)$，则这样的 $y_2$ 不可能成为答案。

因此我们直接单调队列维护，虽然不能保证每个 $y$ 的答案都正确，但能保证每个可能成为答案的 $y$ 的答案都正，因此每个前缀的答案都正确。

那么查询的是就不用在凸壳上二分，直接单调队列维护切点即可。

时间复杂度 $\mathcal O(n\sqrt n)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
#define LL __int128
using namespace std;
const int MAXN=1e5+5;
const ll inf=1e18;
int n,m;
ll a[MAXN],b[MAXN];
struct poi { ll x,y; };
bool chk(poi u,poi v,poi q) { //slope(u,q)<slope(v,q)
	return (LL)(q.y-u.y)*(q.x-v.x)<(LL)(q.y-v.y)*(q.x-u.x);
}
poi st[MAXN];
int hd,tl;
void ins(poi o) {
	while(tl>hd&&chk(st[tl-1],st[tl],o)) --tl;
	st[++tl]=o;
}
ll qry(poi o) {
	if(hd>tl) return inf;
	while(hd<tl&&chk(st[hd+1],st[hd],o)) ++hd;
	return (o.y-st[hd].y)/(o.x-st[hd].x);
}
const int K=360;
ll f[MAXN/K+5][MAXN];
ll sol(int l,int r) {
	if(l%K==0) return f[l/K][r];
	if(r%K==0) return f[r/K][l];
	if(l/K==r/K) {
		ll s=inf; hd=1,tl=0;
		for(int i=l;i<=r;++i) s=min(s,qry({i,a[i]})),ins({i,b[i]});
		return s;
	}
	ll s=min(f[l/K+1][r],f[r/K][l]); hd=1,tl=0;
	for(int i=l;i<(l/K+1)*K;++i) s=min(s,qry({i,a[i]})),ins({i,b[i]});
	for(int i=r/K*K+1;i<=r;++i) s=min(s,qry({i,a[i]})),ins({i,b[i]});
	return s;
}
vector<int> testset(vector<int>A,vector<int>B,vector<int>QL,vector<int>QR) {
	n=A.size(),m=QL.size();
	for(int i=1;i<=n;++i) {
		a[i]=a[i-1]+A[i-1]+(i<n?B[i-1]:0);
		b[i]=b[i-1]+A[i-1]+(i>1?B[i-2]:0);
	}
	for(int o=0,x;o*K<=n;++o) {
		ll *dp=f[o]; dp[x=o*K]=inf;
		hd=1,tl=0,ins({x,b[x]});
		for(int i=x+1;i<=n;++i) dp[i]=min(dp[i-1],qry({i,a[i]})),ins({i,b[i]});
		hd=1,tl=0,ins({-x,-a[x]});
		for(int i=x-1;i>=0;--i) dp[i]=min(dp[i+1],qry({-i,-b[i]})),ins({-i,-a[i]});
	}
	vector <int> ans;
	for(int i=0;i<m;++i) ans.push_back(sol(QL[i],QR[i]+1));
	return ans;
}