前言

牛魔，一开始还读错题了，导致写了满分做法但是对着拿到特殊条件的 30 分的评测结果死活没看明白是哪错了，结果发现是题目读错了。每一段比较的是最大编号的质量，而不是每段质量的最大值。啊啊啊啊啊啊，场上千万不能犯这种错误啊，要不然就亏大发了。

题目解析

题意不写了，直接看题就行，后面那一大坨公式不用看，我看到一大堆公式符号就会似。

我们设体积 $v_i$ 的前缀和为 $s_i=\sum\limits_{j=1}^i v_j$ ，然后设 $0$ 处的质量 $m_0=0$ 。

我们很快能得到一个 DP 的状态转移方程。设 $f_i$ 是将前 $i$ 个金块划分打包的最小代价，初始有 $f_0=0$ 。对于每一个 $i$ ，不难想到可以由 $j~(j<i)$ 转移过来，把 $[j+1,i]$ 这一段打包。然后再加上最大编号质量的条件，就有：

$$ f_i=\min\limits_{j< i, m_j< m_i}f_j+(s_i-s_j-L)^2 $$

然后下面的限制条件较为复杂，暂且不考虑，先考虑这个式子怎么转换。由于题目里有平方项，所以一眼可以想到用斜率优化来表示。

$$ f_i=(-2s_js_i+f_j+2s_jL+s_j^2)+(s_i-L)^2 $$

于是就变成了，设 $j$ 代表的直线是 $y_j=k_j x + b_j$ ，其中 $k_j=-2s_j,b_j=dp_j+2s_jL+s_j^2$ 。然后就变成了找这些直线在 $s_i$ 处的最小值，直接上李超树就完事了，$j<i$ 这个条件就按顺序一个一个一个的加进去就行。最开始别忘了把 $0$ 对应的直线也加进去。

然后注意到 $s_i$ 最高是 $10^9$ ，所以我们还需要对坐标离散化一下。说是要离散化，但是由于 $s_i$ 是单调递增的，所以在李超树上直接把 $i$ 位置的横坐标视为 $s_i$ 就完事了，不用做排序和离散化。

接下来考虑怎么解决 $m_j<m_i$ 这个限制。网上能找到的题解都是用 cdq 分治来解决这一维偏序的。但是我脑子不好，看不懂思密达，有没有更适合宝宝食用的方法呢？当然有！单独的一个李超树无法解决另一维偏序的区间查询问题，那么我们用线段树套李超树不就得了！

外层的线段树按照 $[0,n]$ 的质量维度进行建树。每次 $i$ 的 DP 值确定了之后，将其对应直线插入到外层的 $m_i$ 位置即可。由于李超树动态开点时可以直接存储直线，而不需要开到底端，所以线段树套李超树的空间复杂度是 1 个 $\log$ 而不是 2 个 $\log$ 。即便是 AcWing 只给了 64MB 的空间限制我们一样能过。因为插入是单点插入，所以无脑在外层搜索沿途的李超树上插入即可。查询的时候外层限定范围在 $[0,m_i-1]$ 即可。

时间复杂度 $O(n\log^2 n)$ ，空间复杂度 $O(n\log n)$ ，因为几乎没用 STL ，所以在 AcWing 不开 O2 也能轻松过。

const int N = 100010, LOG_N = 18;
const i64 INF = 1145141919810114514ll;
i64 n, L;
int M[N];
i64 X[N], dp[N];
struct line
{
    i64 k, b;
    inline line(i64 _k = 0, i64 _b = INF) : k(_k), b(_b) {}
    inline i64 f(const i64& x) const { return k * x + b; }
} lin[N];
struct node_in
{
    int lid, lc, rc;
} tri[N * LOG_N];
int icnt;
struct node_out
{
    int rt, lc, rc;
} tro[N << 1];
int ocnt;
void modify_in(int& u, int l, int r, int lid)
{
    if (!u)
        return (void)(u = ++icnt, tri[u].lid = lid);
    int m = (l + r) >> 1;
    if (lin[tri[u].lid].f(X[m]) > lin[lid].f(X[m]))
        std::swap(tri[u].lid, lid);
    if (lin[tri[u].lid].f(X[l]) > lin[lid].f(X[l]))
        modify_in(tri[u].lc, l, m, lid);
    else if (lin[tri[u].lid].f(X[r]) > lin[lid].f(X[r]))
        modify_in(tri[u].rc, m + 1, r, lid);
}
i64 query_in(const int rt, const int& x)
{
    i64 ret = lin[tri[rt].lid].f(X[x]);
    int l = 0, r = n, m = 0, u = rt;
    while (l < r)
    {
        m = (l + r) >> 1;
        (x <= m) ? (u = tri[u].lc, r = m) : (u = tri[u].rc, l = m + 1);
        if (!u)
            return ret;
        ret = std::min(ret, lin[tri[u].lid].f(X[x]));
    }
    return ret;
}
int build_out(int l, int r)
{
    int u = ++ocnt, m = (l + r) >> 1;
    if (l ^ r)
        tro[u].lc = build_out(l, m), tro[u].rc = build_out(m + 1, r);
    return u;
}
void modify_out(int u, int l, int r, int pos, int lid)
{
    modify_in(tro[u].rt, 0, n, lid);
    if (l == r)
        return;
    int m = (l + r) >> 1;
    (pos <= m) ? (modify_out(tro[u].lc, l, m, pos, lid)) : (modify_out(tro[u].rc, m + 1, r, pos, lid));
}
i64 query_out(int u, int L, int R, int l, int r, int x)
{
    if (l > R || r < L)
        return INF;
    if (l <= L && R <= r)
        return query_in(tro[u].rt, x);
    int M = (L + R) >> 1;
    return std::min(query_out(tro[u].lc, L, M, l, r, x), query_out(tro[u].rc, M + 1, R, l, r, x));
}
int main()
{
    n = rd(), L = rd();
    build_out(0, n);
    for (int i = 1; i <= n; ++i)
        X[i] = rd() + X[i - 1];
    for (int i = 1; i <= n; ++i)
        M[i] = rd();
    lin[1] = line(-2 * X[0], dp[0] + 2 * X[0] * L + X[0] * X[0]);
    modify_out(1, 0, n, M[0], 1);
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = query_out(1, 0, n, 0, M[i] - 1, i);
        dp[i] += (X[i] - L) * (X[i] - L);
        lin[i + 1] = line(-2 * X[i], dp[i] + 2 * X[i] * L + X[i] * X[i]);
        modify_out(1, 0, n, M[i], i + 1);
    }
    wr(dp[n]);
}