date: '2023-10-13'
title: 'Solution -「GYM 104128E」Color the Tree'

Desc.

Link.

给出树 $T=(V,E)$, 一个代价数组 $a_0,\dots, a_{n-1}$. 现欲对该树进行黑白染色, 所有节点初始皆为白色, 每次你可以令节点 $u$ 的子树中距离 $u$ 为 $i$ 的节点以 $a_i$ 的代价染为黑色. 问将整棵树染为黑色的最小代价.

$n \leqslant 10^5$.

Sol.

朴素做法即, 设 $f_{u, d}$ 为将子树 $u$ 中距离 $u$ 为 $d$ 的节点染为黑色的最小代价, 直接转移即可. $\mathcal O(n^2)$. 以下是朴素部分的代码:

void dfs2(int u) {
    for (int v : grp[u]) dfs2(v);
    for (int i=0;i<=m-dep[u];++i) dp[u][i] = a[i];
    static ll sum[N + 5];
    memset(sum, 0, (m-dep[u])*8);
    for (int v : grp[u]) {
        for (int i=0;i<=m-dep[v];++i) sum[i] += dp[v][i];
    }
    for (int i=0;i<m-dep[u];++i) chkmin(dp[u][i+1], sum[i]);
}

然后可以发现, 我们对于不同深度染色最小代价的计算是独立的, 于是枚举 $d$, 我们求解将原树中深度为 $d$ 的节点染黑的最小代价. 后面的做法就很暴力了, 直接将深度为 $d$ 的节点拉出来建虚树, 跑朴素 DP 即可. $\mathcal O(n\log_2 n)$ / $\mathcal O(n)$, 根据具体实现复杂度不同.

void solve() {
    int n; cin >> n;
    vi a(n); rds(a);
    const int LG = __lg(n)+1;
    vvi mn(LG);
    mn[0] = a;
    for (int i=1;i<LG;++i) {
        mn[i].resize(n-(1<<i)+1);
        for (int j=0;j<n-(1<<i)+1;++j) mn[i][j] = min(mn[i-1][j], mn[i-1][j+(1<<i-1)]);
    }
    auto getMin = [&](int l, int r) {
        assert(0 <= l && l <= r && r < n);
        int k = __lg(r-l+1);
        return min(mn[k][l], mn[k][r-(1<<k)+1]);
    };
    vvi grp(n);
    for (int i=1,u,v;i<n;++i) {
        cin >> u >> v; u--; v--;
        grp[u].pb(v);
    }
    vvi fa(LG, vi(n+1, n));
    function<void(int)> dfs2 = [&](int u) {
        for (int i=1;i<LG;++i) fa[i][u] = fa[i-1][fa[i-1][u]];
        for (int v : grp[u]) fa[0][v] = u, dfs2(v);
    };
    dfs2(0);
    vi dep(n), dfn(n);
    int timeStamp = 0;
    function<void(int)> dfs = [&](int u) {
        dfn[u] = timeStamp++;
        for (int v : grp[u]) dep[v] = dep[u]+1, dfs(v);
    }; dep[0] = 1; dfs(0);
    auto getLca = [&](int u, int v) {
        if (dep[u] < dep[v]) swap(u, v);
        for (int i=LG-1;i>=0;--i)
            if (fa[i][u] < n && dep[fa[i][u]] >= dep[v]) u = fa[i][u];
        if (u == v) return u;
        for (int i=LG-1;i>=0;--i)
            if (fa[i][u] != fa[i][v]) u = fa[i][u], v = fa[i][v];
        return fa[0][u];
    };
    int m = *max_element(allu(dep));
    vvi idep(m+1);
    for (int i=0;i<n;++i) idep[dep[i]].pb(i);
    ll ans = 0;
    vvi virt(n);
    auto createVirtualTree = [&](vi h) {
        sort(allu(h), [&](int x, int y) {
            return dfn[x] < dfn[y];
        });
        for (int i=0,sz=h.size();i<sz-1;++i) h.pb(getLca(h[i], h[i+1]));
        sort(allu(h), [&](int x, int y) {
            return dfn[x] < dfn[y];
        });
        h.erase(unique(allu(h)), h.end());
        for (int i=0,sz=h.size();i<sz-1;++i) virt[getLca(h[i], h[i+1])].pb(h[i+1]);
        return h[0];
    };
    for (int i=m;i>=1;--i) {
        int rt = createVirtualTree(idep[i]);
        function<ll(int)> dfs3 = [&](int u) {
            if (!virt[u].empty()) {
                ll res = 0;
                for (int v : virt[u]) res += dfs3(v);
                virt[u].clear();
                return min(res, (ll)getMin(i-dep[u], i-1));
            } else return (ll)getMin(0, i-1);
        };
        ans += dfs3(rt);
    }
    cout << ans << "\n";
}

/ 看着蔚蓝的天空被电线分割了 /

/ 天空下的你和我擦肩过 /

/ 就像风起风落 /

/ 曾有一张白纸在面前铺陈着 /

/ 提起笔勾勒出了轮廓 /

—— 孤寂code - 平行 ft. 洛天依

date: '2023-10-13'
title: 'Solution Set -「Nhk R2」'

A

观察数据范围， 我们可以发现 $n \leq 3000, k \leq 10^9$ 指向的是时间复杂度大概率是 $O(n^2)$ 的。 又由于是回文串， 和回文串相关的 $O(n^2)$ 算法最容易想到的就是枚举对称点暴力扩展。

接着再考虑如何处理操作， 如果我们单独有一个回文串， 想要扩展它的长度， 最优的方法就是在对称点进行操作， 这样每次操作后序列依旧回文， 如 $\texttt{bab}$ 可以操作为 $\texttt{baab}$ ， $\texttt{bcbbcb}$ 可以操作为 $\texttt{bcbbbcb}$ 。

但是如果不是整个序列为回文串的话， 我们直接找最长回文子串然后在对称点进行操作不一定最优， 所以需要考虑在两侧进行操作（因为不在回文串两侧一定不是最优）， 这时候有两种情况， 一种是可以通过在一侧进行操作后就能继续匹配， 如 $\texttt{bbabc}$ 可以对右侧的 $\texttt{b}$ 操作后扩展回文串长度， 回文串由 $\texttt{bab}$ 变为 $\texttt{bbabb}$ 这个时候我们执行这个操作， 因为这次操作和在对称点进行操作比一定不劣， 如果两端加数都不能继续匹配， 如 $\texttt{cbabd}$ ， 就停止两侧的扩展， 因为此时想要在两侧操作后能扩展， 当且仅当同时对两边进行相同次数的操作， 这样和在对称点操作比起来一定不优。

最后， 如果我们有一段到了序列的首或尾， 我们直接选择在中间操作， 一直操作到长度等于 $k$ 。

B

从题目最强的限制入手，考虑如何使得每个点恰好处于一个环上？

这是一个很典的 trick，对于任何在环上的点 $p$，出入度都为 $1$，于是将它拆成两个点，记为 $p_{in}, p_{out}$。原图上的一条边 $(u, v)$ 在拆点后的图上就表示为 $(u_{out}, v_{in})$，如果要满足限制，当且仅当该图存在完美匹配。

现在加入双边权的限制，这是 0/1 分数规划 的模型，具体地，我们二分答案 $mid$，如果有解，则满足 $\large\frac{\sum_{i \in E} a_i }{\sum_{i \in E} b_i } \ge mid$，化一下式子变成 $\sum_{i \in E} a_i - mid \cdot {\sum_{i \in E} b_i } \ge 0$，于是重新对每一条边赋权为 $c_i = a_i - mid \cdot b_i$，检验是否有解直接跑 KM 即可。

复杂度取决于 KM 的实现方式，较优秀的为 $\Theta(n^3) \log V$，其中 $V$ 是 $a_i, b_i$ 的值域。

C

让我们来挖掘一些性质。不妨设 $n=2$，它的 $0\sim 2^n-1$ 的序列用二进制表示即为:

$$ \begin{matrix} 00 \\ 01 \\ 10 \\ 11 \\ \end{matrix} $$

那么当 $n=3$ 时，就相当于是在这个序列前加了一位，这一位可能是 $1$ 也可能是 $0$，列出来即为:

$$ \begin{matrix} 0\quad 00 \\ 0\quad 01 \\ 0\quad 10 \\ 0\quad 11 \\ 1\quad 00 \\ 1\quad 01 \\ 1\quad 10 \\ 1\quad 11 \\ \end{matrix} $$

所以可以发现:

1. 异或值是对称的；
2. 其最中间的数值是 $2^n-1$。

我们再对比上面 $n=2$ 与 $n=3$ 的区别，可以发现，题目的问题可以递推求解。

我们设第一个问题是的答案是 $f$，第二个问题是 $g$。那么有以下式子:

$$ \begin{cases} f_i=2\times f_{i-1}+\binom{n}{i} \\ \\ g_i=2\times g_{i-1}+i\binom{n}{i} \end{cases} $$

我们把上面第一个式子化为求和式，即为 $\displaystyle\sum_{i=1}^n2^{n-i}\binom{n}{i}$，又因为 $\displaystyle\binom{n}{i}=\binom{n}{n-i}$，所以 $\displaystyle=\sum_{i=1}^n2^{n-i}\binom{n}{n-i}\displaystyle=-2^n\times\binom{n}{n}+\sum_{i=0}^n2^{n-i}\binom{n}{n-i}$，换一下元，即 $\displaystyle-2^n\times\binom{n}{n}+\sum_{i=0}^n2^{i}\binom{n}{i}$，又通过二项式定理，得到原式即 $(2+1)^n-2^n=3^n-2^n$，用快速幂求解即可。

我们把上面第二个式子化为求和式，即为 $\displaystyle\sum_{i=1}^ni\times2^{n-i}(2^i-1)\binom{n}{i}$ 因为加上 $i=0$ 其值不变故可写为 $\displaystyle\sum_{i=0}^ni\times2^{n-i}(2^i-1)\binom{n}{i}$，将括号拆开 $\displaystyle\sum_{i=0}^ni2^{n}\binom{n}{i}-\sum_{i=0}^ni2^{n-i}\binom{n}{i}$ 我们将其看作左右两个式子求解，先看左边，即为 $\displaystyle\sum_{i=0}^ni2^{n}\binom{n}{i}$，将 $2^n$ 提出，即 $\displaystyle2^{n}\sum_{i=0}^ni\binom{n}{i}=2^{n-1}(\sum_{i=0}^ni\binom{n}{i}+\sum_{i=0}^ni\binom{n}{i})$ 再将式子括号右边的求和式通过 $\binom{n}{i}=\binom{n}{n-i}$ 变换一下，即 $\displaystyle 2^{n-1}(\sum_{i=0}^ni\binom{n}{i}+\sum_{i=0}^ni\binom{n}{n-i})$ 再换元，即 $\displaystyle2^{n-1}(\sum_{i=0}^ni\binom{n}{i}+\sum_{i=0}^n(n-i)\binom{n}{i})$ 再将括号中的数加起来，即 $=2^{n-1}\sum_{i=0}^nn\binom{n}{i}$，再将 $n$ 提出，即 $\displaystyle n2^{n-1}\sum_{i=0}^n\binom{n}{i}$ 再用二项式定理，可化为：$n2^{n-1}2^n=n2^{2n-1}$。

我们再考虑右边的式子 $\displaystyle-\sum_{i=0}^ni2^{n-i}\binom{n}{i}$，给其加上一个 $\displaystyle n\sum_{i=0}^{n}2^{n-i}\binom{n}{i}$，再减去，即 $\displaystyle\sum_{i=0}^{n}(n-i)2^{n-i}\binom{n}{i}-n\sum_{i=0}^{n}2^{n-i}\binom{n}{i}$ 右边式子的结果在上面求解第一个问题已经算过，为 $n*3^n$，化简即为 $\displaystyle\sum_{i=0}^{n}(n-i)2^{n-i}\binom{n}{i}-n*3^n$ 再换元，即为 $\displaystyle\sum_{i=0}^{n}i2^i\binom{n}{i}-n*3^n$ 再通过组合恒等式$\displaystyle\binom{n}{m}=n/m*\binom{n-1}{m-1}$，可化为 $\displaystyle\sum_{i=0}^{n}n2^i\binom{n-1}{i-1}-n*3^n$，提出 $2*n$，即为 $\displaystyle 2n\sum_{i=0}^{n}2^{i-1}\binom{n-1}{i-1}-n*3^n$ 再换元，即为 $\displaystyle 2n\sum_{i=0}^{n-1}2^{i}\binom{n-1}{i}-n*3^n$ 再用二项式定理，可化为 $\displaystyle 2n*3^{n-1}-n*3^n=-n*3^{n-1}$。

综上所述，第二问答案为 $n2^{2n-1}-n*3^{n-1}$，可用快速幂求解。

D

一个结论是任意无向图度数为奇数的点有偶数个。因为一条边会使得度数总和增加 $2$，度数总和永远是偶数。

所以如果建一个虚点向所有度数为奇数的点连边，则这个新图存在欧拉回路。

考虑初始图为二分图。然后加上虚点。

考虑从虚点出发，每走一条边，就染成跟上一条边不相同的颜色，即黑白间隔染色。则不被虚点连向的点（度数为偶数），每次进入这个点就会出这个点，边能一一对应。设初始图中 $a_x$ 表示 $x$ 点为端点的边有 $a_x$ 条被染成白色，$b_x$ 表示以 $x$ 为端点的边有 $b_x$ 条被染成黑色，则对于度数为偶数的点 $|a_x-b_x|=0$。对于度数为奇数的点，加上虚点连向的边，一样可以做到一进一出一一对应。由于虚点连向的边不产生贡献，所以 $|a_x-b_x|=1$。

则二分图 $\sum_x |a_x-b_x|$ 的答案为图中度数为奇数的点的个数。

考虑本题。驿站发件处看做左部点，收件处看做右部点，是一个二分图。所以可以用上述结论。

对于一个询问新加入的点，会对其右上的点的度数产生影响，而新加入点的度数为左下的点数。

首先二维数点求出初始答案，记为 $ans1$。然后记录每个点的度数奇偶性。

对于新加入的点分为三个二维数点。

第一个算新加入点的度数，记为 $deg1$。

第二个算新加入点右上角的点数，记为 $cnt1$。

第三个算新加入点右上角度数为偶数的点数，记为 $cnt2$

新答案为 $ans1+[deg1\%2=1]+cnt2-(cnt1-cnt2)$。

E

前三种操作维护起来比较简单，这里就略过了，第四种操作只需要注意到「最多操作 $\log_2 n$ 次」的性质即可。

主要来看询问部分。

整个图的形状就是一根「主链」上挂了若干根「副链」，由此可以发现这个图中的最长简单链的长相一定类似如下的图示：

$$ \cdots{\color{black}\bullet\ \bullet\ \bullet\ }\color{black}\bullet\ {\color{black}\bullet\ }{\color{red}{\bullet\ \bullet\ \bullet\ \bullet\ \bullet\ }}{\color{black}\bullet\ }\color{black}\bullet\ {\color{black}\bullet\ \bullet\ \bullet}\cdots\ \\ \cdots{\color{black}\bullet\ \color{red}{\bullet\ }\color{black}\bullet\ \bullet\ \bullet\ \color{red}{\bullet\ }}\color{black}\bullet\cdots \\ \cdots{\color{black}\bullet\ \color{red}{\bullet\ }\color{black}\bullet\ \bullet\ \bullet\ \color{red}{\bullet\ }}\color{black}\bullet\cdots \\ \cdots{\color{black}\bullet\ \color{red}{\bullet\ }\color{black}\bullet\ \bullet\ \bullet\ \color{red}{\bullet\ }}\color{black}\bullet\cdots \\ \vdots $$

其中红色的点是图中的最长链。那么我们考虑暴力怎么做。我们处理出两个东西，一个是上面那个图的第一层的权值前缀和 $a_i$，以及不包含第一层元素的每一条单链的权值和 $b_i$，那么答案即 $\max\limits_{1\leqslant i\leqslant j\leqslant n}\{a_j-a_{i-1}+b_i+b_j\}$。此时就可以考虑平衡树套线段树了，平衡树维护第一层的结点，线段树维护每条链除第一层结点外的部分，维护方法参见最大子段和。

F

记所有有颜色的边的属性集合 $S$ 。

首先在外层容斥，枚举 $S\in [0,2^w)$，计算被覆盖的的边中不包含 $S$ 中属性，并且没有被覆盖的边的数目恰好为 $i$ 的配对方案数。

暴力的 DP 做法是记录子树内还没有被匹配的点的数目，复杂度$O(n^5)$，不能通过。出题人特意卡了这种做法。

如果一条边没有覆盖，那么所有点对间的路径都不能经过这条边，这样我们可以把一个连通块分成两个子联通块进行求解。但是这样就要记录连通块里面所有的点，无法通过

考虑二项式反演。记 $g(i)$ 表示钦定断了 $i$ 条边（即$i$条边没有被覆盖）的方案数，$f(i)$ 表示恰好断了 $i$ 条边的方案数，注意这里的下标 $i$ 不包含一定不被覆盖的边。那么有：

$g(i)=\sum _{j=i}^{n-1}\binom{j}{i}f(j)\Rightarrow f(i)=\sum_{j=i}^{n-1}(-1)^{j-i}\binom{j}{i}g_j$

而 $g(i)$ 是好算的，也就是剩下的每个连通块内部任意连边的方案数的乘积

记 $h(n)$ 表示大小为 $n$ 的连通块任意连边的方案数，如果 $n$ 为奇数那么答案是 $0$，如果 $n$ 为偶数那么答案是 $(n-1)\times (n-3)\times ...\times 1$

考虑 DP。设 $dp(u, i, j)$ 表示以 $u$ 为根的子树，已经断了 $i$ 条边，连通块大小为 $j$ 的方案数。对于一条边 $(u,v,w)$ 转移式子如下：

$1.1$ $dp(u, i, j) \times dp(v, i_2, j_2) \times h(j_2) \to dp(u, i + i_2+1, j)$

$1.2$ 如果 $w\notin S$，$dp(u,i,j)\times dp(v,i_2,j_2)\to dp(u,i+i_2,j+j_2)$

这个 DP 的时间复杂度上界是 $O(n^4)$ 的，因此总复杂度 $O(2^wn^4)$ 。

但是注意到每个连通块大小都是必须偶数，因此常数极小，实测单次 DP 计算量在 $10^6$ 左右，链的情况可以卡满。注意要把 DP 值为 0 的状态跳过，否则无法通过

数据里面造了一些几条链并起来的情况，暴力要跑 4s 以上，std 能稳定在 0.5s 内出解。随机数据下基本卡不了。如果有人暴力冲过去了或者正解被卡常了，出题人在这里谢罪:(

考虑到打这场比赛的大佬肯定还是比较多的，如果场切这道题的大佬们有更精确的分析复杂度的方式欢迎赛后分享。

date: '2023-10-08'
title: 'Solution Set -「LOC 4293」'

Link.

A. 特种训练 (train)

写不来这种 Ad-hoc 题.

B. 红色改造 (modification)

可以参考论文 万成章 - Astral Birth 解题报告

把相同连续段合并起来, 将原 $0/1$ 序列转化成一个由二元组 $(0/1, c_i)$ 组成的长度为 $m$ 的序列, 问题有转化一:

• 选出尽量长的子序列, 其段数不超过 $k+1$ ($+1$ 的原因是贡献分为三种, 打过朴素的 DP 都知道), 则子序列长度和为答案.

倒过来考虑, 我们需要从中选择一些元素删去, 有以下的 Observation:

• Observation 1: 我们不会删除相邻的元素.

那么有转化二:

• 对于每个 $k$, 选择一些价值之和为 $k$ 的元素并将它们删除, 要求元素两两不相邻, 且长度之和最小. 元素的价值就是 $1$ 或 $2$, 第一个和最后一个元素的价值为 $1$, 其余为 $2$.

然后就是一个经典的反悔贪心问题.

D. 车站爆破 (bomb)

居然可以维护操作序列... 还是见识浅薄...

date: '2023-09-28'
title: 'Solution -「模拟赛」草莓蛋糕'

$\max(a_x + a_y, b_y + b_x)$ 的贡献形式不是独立的，并不好进行分析。考虑通过分类讨论将 $\max$ 拆开。若令 $h_i = a_i - b_i$，$h'_i = b_i - a_i$，可以发现若 $h_x \geqslant h'_y$ 取值则为 $b_x + b_y$，反之亦然。

注意到 $h$ 本身自带一个一维偏序关系，于是放到数轴上用线段树维护，每个节点维护 $a_x$，$a_y$，$b_x$，$b_y$ 的最小值，以及区间的答案。修改操作在线段树的叶子节点维护四个 std::multiset 即可。

const int N = 1e6;
const int INF = numeric_limits<int>::max();
int Q, opt[N + 100], cat[N + 100], a[N + 100], b[N + 100];
using MSET = multiset<ll>;
struct node {
    ll mn[4], ans;
    node() : ans(INF) {
        for (int i = 0; i < 4; ++i) mn[i] = INF;
    }
};
struct SegmentTree {
#define NODE int u, int l, int r
#define mid (((l) + (r)) / 2)
#define ls (u * 2)
#define rs (u * 2 + 1)
#define LC ls, l, mid
#define RC rs, mid + 1, r
#define SetAcc(id, i) (*leaves[id][i].begin())
    const int __n;
    vector<node> body;
    vector<array<MSET, 4>> leaves;
    void pullup(int u) {
        body[u].ans = min({body[ls].mn[2] + body[rs].mn[0], body[ls].mn[1] + body[rs].mn[3], body[ls].ans, body[rs].ans});
        for (int i = 0; i < 4; ++i) body[u].mn[i] = min(body[ls].mn[i], body[rs].mn[i]);
    }
    void upd(int pos, NODE) {
        if (l == r) {
            for (int i = 0; i < 4; ++i) body[u].mn[i] = SetAcc(l, i);
            body[u].ans = min(SetAcc(l, 0) + SetAcc(l, 2), SetAcc(l, 1) + SetAcc(l, 3));
        } else mid >= pos ? upd(pos, LC) : upd(pos, RC), pullup(u);
    }
public:
    void upd(int pos) {upd(pos,1,1,__n);}
    int Ask() {return body[1].ans;}
    SegmentTree(int n) : __n(n), body(4 * n + 5), leaves(n + 5) {
        rep (j, 1, n) for (int i = 0; i < 4; ++i) leaves[j][i].emplace(INF);
    }
};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    rd(Q);
    bsi dat;
    rep (i, 1, Q) {
        rd(opt[i], cat[i], a[i], b[i]);
        dat.pb(cat[i] == 0 ? a[i] - b[i] : b[i] - a[i]);
    }
    sort(allu(dat)), dat.resize(distance(dat.begin(), unique(allu(dat))));
    auto getter = [&](int x) -> int {
        return distance(dat.begin(), lower_bound(allu(dat), x)) + 1;
    };
    const int dataLength = dat.size();
    SegmentTree treeask(dataLength);
    rep (i, 1, Q) {
        int pos = getter(cat[i] == 0 ? a[i] - b[i] : b[i] - a[i]);
        assert(1 <= pos && pos <= dataLength);
        auto& cur = treeask.leaves[pos];
        int idx = 2 * cat[i];
        if (opt[i] == 1) cur[idx].emplace(a[i]), cur[idx + 1].emplace(b[i]);
        else cur[idx].erase(cur[idx].find(a[i])), cur[idx + 1].erase(cur[idx + 1].find(b[i]));
        treeask.upd(pos);
        int res = treeask.Ask();
        if (res >= INF) cout << "-1\n";
        else cout << res << "\n";
    }
}

  link．

  单次询问的做法是平凡的，令 $f_i(k)$ 表示将前 $i$ 个元素划分出了 $k$ 段的最大值，有转移：

$$ f_i(k) = \max\{f_{i-1}(k), \max_{0 \leqslant j < i} \{f_j(k-1)+s_i-s_j\}\} $$

  其中 $s$ 是前缀和．研究函数 $g(k) = f_n(k)$，可以发现所有的 $(k, g(k))$ 构成了一个凸包，证明考虑构造一个费用流模型：

将所有元素 $a_i$ 分拆成 $u_i$ 与 $v_i$ 两个点，令四元组 $\lang u, v, c, w\rang$ 为费用流网络上的一条边．有：

$$ V_N = [1, n] \cup \{s, t\} \\ E_N = \{(u_i, v_i) \mid i \in [1, n]\} \cup \{(v_i, u_{i+1}) \mid i\in [1, n)\} \cup\{(s, u_i) \mid i \in [1, n]\} \cup \{ (v_i, t) \mid i \in [1, n] \} \\ \begin{cases} c(u_i, v_i) = 1, w(u_i, v_i) = a_i, i \in [1, n] \\ c(v_i, u_{i+1}) = 1, w(v_i, u_{i+1}) = 0, i \in [1, n) \\ c(s, u_i) = c(v_i, t) = 1, w(s, u_i) = w(v_i, t) = 0, i \in [1, n] \end{cases} $$

由于最大费用流每次增广的费用是递减的，因此 $g(k)$ 的斜率递减．

  再考虑多次询问，我们使用线段树来维护分治的过程．具体而言，线段树上的每一个结点维护的是 $g_{[l, r]}(k)$ 表示只考虑原序列的 $[l, r]$ 这一部分的 $g(k)$．但是你注意到一个事情，$[l, m]$ 和 $(m, r]$ 这两个区间要是合并成了 $[l, r]$ 这个区间，我们需要考虑跨过中点的情况．所以线段树上的每个结点一共要维护四个凸包，分别是 $g_{[l, r]}(k, 0/1, 0/1)$，表示考虑区间 $[l, r]$ 上左右端点分别有没有被划分入某一段里面的情况．

  现在我们来考虑怎么合并线段树上某个结点的两个子结点里面的四乘二等于八个凸包．注意到只有左儿子取了右端点，且右儿子取了左端点的情况合并比较特殊，其他的 15 种情况都是同理的．因为这时，左右儿子合并出来的凸包会少一段（左儿子的右端点和右儿子的左端点合并成了一段）．我们写出比较普适的另外 15 种情况（以下方程没有写出限制条件）的转移：

$$ g_{[l, r]}(i+j, 0/1, 0/1) = \max\{g_{[l, m]}(i, 0/1, 0/1)+g_{(m, r]}(j, 0/1,0/1)\} $$

  特殊情况：

$$ g_{[l, r]}(i+j-1, 0/1, 0/1) = \max\{g_{[l, m]}(i, 0/1, 0/1)+g_{(m, r]}(j, 0/1,0/1)\} $$

  这个转移怎么维护呢？看起来好像要 $O((r-l+1)^2)$ 的样子．但是如果你仔细看就会发现这是个向量加法的形式，即 $(i+j, g_3(i+j)) = (i, g_1(i))+(j, g_2(j))$，使用凸包的 Minkowski Sums 即可线性把加法做出来，再线性取一遍 max 即可．

  到这里我觉得这个题已经足够傻逼了，但这混账 300iq 比我想象中更傻逼．

  我们继续看怎么回答询问．考虑暴力，即把询问区间 $[L, R]$ 在线段树上拆出来的 $O(\log_2(R-L+1))$ 个子区间合并起来，直接取合并出来的凸壳的 $g(k)$ 就是答案．这样合并单次询问的复杂度必然与询问区间长度相关．

  再考虑不直接合并这些凸包，采用 wqs 二分去掉各个凸包选择的段数之和必须为 $k$ 这一限制，那么每个凸包可以各自独立的贪心选择最优解（其实就是各凸包与二分给出的斜率直线切点）再加和得到答案．需要注意的是每个结点四个凸包都要考虑．$O(q \log_2^3 n)$．

  考虑进一步的优化，就是平行 wqs 二分了．因为二分给出的斜率是单调的，因此各个凸包的切点变化也是单调的，使用一个指针维护而不是二分地去找可以剩一个 log．$O(q\log_2^2 n)$．

  我不知道怎样的冤种会去写这种答辩．