我咋还没找到

· · 题解

题意

给定 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();
}