自动搬运

查看原文

来自洛谷，原作者为

	jun头吉吉 alive

搬运于2025-08-24 22:47:43，当前版本为作者最后更新于2023-05-31 10:12:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意

给定 $n,m,x_1,\dots,x_n,a_1,\dots,a_n,y_1,\dots,y_m,b_1,\dots,b_m$，有 $T$ 次询问，每次给出 $c$，你需要找到一组 $i_1,i_2,j_1,j_2$ 满足 $1\le i_1\le i_2\le n,1\le j_1\le j_2\le m$，$(x_{i_2}-x_{i_1})(b_{j_1}+b_{j_2})+(y_{j_2}-y_{j_1})(a_{i_1}+a_{i_2})\le c$，使得 $(x_{i_2}-x_{i_1})(y_{j_2}-y_{j_1})$ 最大，并输出最大值。

$1\le n,m\le5000,T\le 100,1\le a_i,b_i\le 10^7,c\le 10^{12}$

$1\le x_1< \dots < x_n\le 10^5,1\le y_1<\dots<y_m\le 10^5$

题解

记 $L=10^5$。

设 $va_v$ 表示 $x_{j}-x_i=v$ 的最小的 $a_i+a_j$ 值，$vb$ 同理，这两个显然可以用 $\mathcal O(n^2+m^2)$ 求出。那么我们要做的等价于：

$$\begin{array}{cc} \max&i\times j\\ \text{s.t.} &i\times vb_j+j\times va_i\le c \end{array} $$

如果给定 $(i,va_i)$ 只需要判断后一个条件是否满足的话，显然可以对 $(i,vb_i)$ 建立下凸壳，在凸包上二分找到最小值，单次查询时间复杂度为 $\mathcal O(\log L)$。

然后我们枚举 $(i,va_i)$，是可以在 $\mathcal O(\log^2 L)$ 的复杂度找到最大的 $j$ 满足条件的，就是我们可以判断存不存在 $j\ge x$ 满足条件，对这个后缀建立凸包，和上面一样二分判断即可。

后缀凸包其实就是从后往前建凸包，往栈里加点和删点就等价于是在树上新增一个儿子或者跳回父亲，最后得到一棵 $\mathcal O(L)$ 个节点的树，每一个后缀凸包就对应一条到根的链。

当然这样单次询问 $\mathcal O(L\log^2L)$ 是过不去的。这个二分看起来很蠢。我们考虑从 $1$ 到 $L$ 枚举 $j$，然后找到最大的 $i$ 使得后缀凸包存在一个点满足 $\le c$，随着 $j$ 的增大 $i$ 是减小的，所以总的判断次数是 $\mathcal O(L)$ 的，也就做到了 $\mathcal O(L\log L)$ 单次询问。

代码

const int N=5e3+10,L=1e5,M=L+10,K=18;
const int inf=0x3f3f3f3f;
int n,m,T,mx,x[N],a[N],y[N],b[N];
int va[M],vb[M],fa[M][K];ll c;
struct point{
	int x,y;point(int x=0,int y=0):x(x),y(y){}
	point operator-(point rhs){return point(x-rhs.x,y-rhs.y);}
	ll operator*(point rhs){return 1ll*x*rhs.y-1ll*y*rhs.x;}
}st[M];int top;
ll get(int i,int j){return 1ll*i*vb[j]+1ll*j*va[i];}
bool chk(int i,int j){
	// x>=j  i bx + x ai 的最小值
	for(int l=K-1;~l;l--)if(fa[fa[j][l]][0]&&get(i,fa[j][l])>=get(i,fa[fa[j][l]][0]))j=fa[j][l];
	if(fa[j][0]&&get(i,fa[j][0])<=c)return 1;
	return get(i,j)<=c;
}
void work(){
	ll ans=0;
	for(int j=1,i=L;j<=L&&i;)
		if(vb[j]==inf)j++;
		else if(va[i]==inf||!chk(i,j))i--;
		else chkmx(ans,1ll*i*j),j++;
	writeln(ans);
}
signed main(){
	read(n,m,T);memset(va,0x3f,sizeof va);memset(vb,0x3f,sizeof vb);
	readArr(x+1,n);readArr(a+1,n);readArr(y+1,m);readArr(b+1,m);
	for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)chkmn(va[x[j]-x[i]],a[i]+a[j]);
	for(int i=1;i<m;i++)for(int j=i+1;j<=m;j++)chkmn(vb[y[j]-y[i]],b[i]+b[j]);
	for(int i=L;i;i--)if(vb[i]!=inf){
		point p(i,vb[i]);
		while(top>=2&&(st[top]-p)*(st[top-1]-p)<=0)top--;
		if(top)fa[i][0]=st[top].x;
		st[++top]=p;
	}
	for(int i=1;i<K;i++)for(int j=1;j<=L;j++)fa[j][i]=fa[fa[j][i-1]][i-1];
	while(T--)read(c),work();
}