P11587 题解

· · 题解

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。

数据范围：$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;
}