题解：P16680 [CSPro 27] 高维亚空间超频物质变压缩技术

· · 题解

题意简述

把数组划分为若干连续段。每段代价是该段元素和与 L 之差的平方。所有段的右端点对应的 m_i 必须严格递增，求最小总代价。

解题思路

记体积的前缀和为：

s_i=\sum_{j=1}^{i}v_j

令 f_i 表示前 i 块黄金的最小合法代价，且最后一段在 i 结束。设上一段的右端点为 j，则最后一段为 [j+1,i]。合法条件为 j<i 且 m_j<m_i。

补充边界状态 s_0=f_0=m_0=0。转移为：

f_i=\min_{0\le j<i,m_j<m_i}\left(f_j+(s_i-s_j-L)^2\right)

直接枚举 j 需要二次时间。把与 j 无关的部分提出，得到：

f_i=(s_i-L)^2+\min_{0\le j<i,m_j<m_i}\left(-2s_js_i+f_j+s_j^2+2Ls_j\right)

每个已计算的决策点 j 可以看作一条直线。它的斜率和截距分别为：

\begin{aligned} k_j & =-2s_j \\ b_j & =f_j+s_j^2+2Ls_j \end{aligned}

计算 f_i 时，在横坐标 s_i 查询所有满足 m_j<m_i 的直线最小值。按照 i 从小到大计算，并在求出 f_i 后插入直线。这样会自然满足 j<i，只剩关于 m_j 的前缀限制。

用树状数组维护 m 这一维。为了同时容纳 m_0=0，把决策点 j 插入位置 m_j+1。查询位置 m_i 的树状数组前缀时，恰好取得：

m_j+1\le m_i\iff m_j<m_i

因此，树状数组的每个结点维护一组直线。单点加入一条直线时，沿 add 路径把它放入 O(\log n) 个结点；查询前缀时，沿 sum 路径询问 O(\log n) 个结点并取最小值。

还要快速维护每个结点中的直线集合。因为所有 v_i 都为正数，所以 s_i 严格递增。直线按 i 插入时，斜率 -2s_i 严格递减；查询横坐标 s_i 也严格递增。

每个树状数组结点都可以保存一个下凸包。插入时不断删除末尾的冗余直线。查询时用一个指针比较当前直线和下一条直线，下一条不劣时就右移。某条直线在每个凸包中至多加入、删除一次，查询指针也只会单向移动。

设三条直线 a,b,c 的斜率依次递减。判断 b 是否冗余时使用交叉相乘：

(b_b-b_a)(k_b-k_c)\ge(b_c-b_b)(k_a-k_b)

这样不需要浮点除法。代价和交叉乘积可能超过 long long。因此，动态规划值、前缀和与直线参数都使用 __int128。

树状数组的每次加入和查询会访问 O(\log n) 个凸包。凸包内部是均摊常数操作。因此，总时间复杂度为 O(n\log n)，空间复杂度为 O(n\log n)。

正确性证明

先证明动态规划转移。任意合法划分都存在唯一的最后一段 [j+1,i]。此前各段的最优代价为 f_j，最后一段代价为 (s_i-s_j-L)^2。两个相邻段的右端点质量必须满足 m_j<m_i。因此，转移恰好枚举了所有合法的最后一段起点，没有遗漏或加入非法方案。

再证明树状数组查询范围。决策点 j 被插入位置 m_j+1，查询的前缀右端点是 m_i。它被查询到当且仅当 m_j+1\le m_i，也就是 m_j<m_i。直线只会在计算完 f_j 后插入，所以被查询到时还必有 j<i。

最后证明凸包查询。平方展开后，决策点 j 对当前状态的贡献等于直线 k_jx+b_j 在 x=s_i 处的值。各凸包保留的恰是所有可能成为最小值的直线。斜率按严格递减顺序插入，横坐标按严格递增顺序查询，故最优直线的位置不会向左移动。单调指针返回的就是该凸包内的最小值。

树状数组覆盖全部且仅有合法决策点，每个凸包又准确返回局部最小值。因此，算法得到的 f_i 与动态规划定义一致，最终的 f_n 即为答案。

参考代码

#include <bits/stdc++.h>
using namespace std;

__extension__ using i128=__int128;
const int N=100005;
const i128 inf=i128(1)<<120;
struct Line
{
    i128 k,b;
};
i128 calc(Line a,i128 x)
{
    return a.k*x+a.b;
}
bool bad(Line a,Line b,Line c)
{
    return (b.b-a.b)*(b.k-c.k)>=(c.b-b.b)*(a.k-b.k);
}
struct Hull
{
    vector<Line> q;
    int pos=0;
    void add(Line a)
    {
        while(q.size()>=2&&bad(q[q.size()-2],q.back(),a))
        {
            q.pop_back();
            if(pos==q.size())pos--;
        }
        q.push_back(a);
    }
    i128 ask(i128 x)
    {
        if(q.empty())return inf;
        while(pos+1<q.size()&&calc(q[pos+1],x)<=calc(q[pos],x))pos++;
        return calc(q[pos],x);
    }
};
struct BIT
{
    Hull c[N];
    void add(int u,Line a){while(u<N){c[u].add(a);u+=u&-u;}}
    i128 sum(int u,i128 x){i128 res=inf;while(u){res=min(res,c[u].ask(x));u-=u&-u;}return res;}
}T;
int m[N];
i128 s[N],f[N];
void print(i128 x)
{
    if(x>=10)print(x/10);
    cout<<int(x%10);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,L;
    cin>>n>>L;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        s[i]=s[i-1]+x;
    }
    for(int i=1;i<=n;i++)cin>>m[i];
    T.add(1,{0,0});
    for(int i=1;i<=n;i++)
    {
        f[i]=(s[i]-L)*(s[i]-L)+T.sum(m[i],s[i]);
        T.add(m[i]+1,{-2*s[i],f[i]+s[i]*s[i]+2*L*s[i]});
    }
    print(f[n]);
    cout<<'\n';
    return 0;
}