wqs 二分

引入

wqs二分，又称带权二分、带权wqs、凸完全单调性，是国家集训队成员王钦石在 2012 年的集训队作业 中提出的一种二分方法。

由于此方法在 IOI 2016 Aliens 中得到首次实战运用，因此国外将其称为 Aliens' Trick。

尽管wqs二分被划到DP专栏，但wqs二分并不是只为DP而生，划分到这里的原因有两个：

1. 广泛应用在 DP 优化；
2. 其思想与 斜率优化DP 类似，都运用了建立在凸包上的单调性。

内容

wqs二分主要用于解决形如“强制取 \(k\) 个物品，使得总价值最大”的问题。

我们记 \(f_k\) 为强制取 \(k\) 个物品时的最大总价值，可以发现：

\[f_{i + 1} - f_i \leq f_i - f_{i - 1}\]

也就是说，如果将一系列点 \((x, f_x)\) 画在平面直角坐标系中，得到的图形将会是一个上凸包。

这是因为，如果存在一种选法，使得 \(f_{i + 1} - f_i > f_i - f_{i - 1}\)，设 \(w_i = f_i - f_{i - 1}, w_{i + 1} = f_{i + 1} - f_i\)，也就是第 \(i\) 轮与第 \(i + 1\) 轮多选的物品，那么 \(w_i < w_{i + 1}\)，这意味着，我们完全可以先选择 \(w_{i + 1}\)，再选择 \(w_i\)，这会使 \(f_i\) 更优，这时就能得到 \(f_{i + 1} - f_i \leq f_i - f_{i - 1}\)。

假设去掉选择数的限制得到了一个求最优解的算法，但此时选择数并不一定是我们想要的，如何影响选择数呢？

我们可以对每次的选择都人为加一个额外贡献（也可以是代价） \(\Delta\)，如果 \(\Delta\) 为正，那么显然选择数会增长，反之，如果 \(\Delta\) 为负，那么选择数会降低。

于是，我们可以二分这个 \(\Delta\)，每次记录选择数以调整 \(\Delta\) 的值，最后再去除 \(\Delta\) 带来的贡献（或代价）。

这就是 wqs 二分的核心，它还有一个几何意义：

事实上，我们每次加一个额外贡献（也可以是代价）\(\Delta\)，假设选择数是 \(x\)，结果是 \(y\)，那么会有 \(y = f_x - \Delta x\)，这就是告诉我们，wqs二分的几何实质是在 \((x, f_x)\) 组成的上凸包上二分斜率求切点。

唯一需要注意的是，凸包上可能有点共线，此时需按具体情况处理。

下面给出一些例题：

例题

P2619 [国家集训队] Tree I

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 \(need\) 条白色边的生成树。

题目保证有解。

对于 \(5\%\) 的数据，\(V\leq 10\)。

对于另 \(15\%\) 的数据，\(V\leq 15\)。

对于 \(100\%\) 的数据，\(V\leq 5\times10^4,E\leq 10^5\)。

所有数据边权为 \([1,100]\) 中的正整数。

很板子的题目。

我们将边按黑白分为两类，调整白边的权值，每次跑 Kruskal 求最小生成树并记录白边数量即可。

这里有一个小优化：我们可以先对两类边分别排序，由于白边每次加上的是统一的偏移量，因此相对大小不会改变，这样每次 Kruskal 的排序就可以变为归并。

实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int MAXN = 1e5 + 10;
class DSU
{
    int f[MAXN];
    int getf(const int x) { return f[x] = (f[x] == x ? x : getf(f[x])); }

public:
    void init(int n)
    {
        for (int i = 1; i <= n; i++) f[i] = i;
    }
    bool qry(const int x, const int y) { return getf(x) == getf(y); }
    void merge(int x, int y) { x = getf(x), y = getf(y), f[y] = x; }
} dsu;
struct edge
{
    int u, v, w, c;
} e[MAXN], e1[MAXN], e2[MAXN]; // e2 m2 -> c = 0
int ans, n, m, k, cnt, sum, m1, m2;
void kruskal()
{
    merge(e1 + 1, e1 + 1 + m1, e2 + 1, e2 + 1 + m2, e + 1, [](edge x, edge y)
          { return x.w == y.w ? x.c < y.c : x.w < y.w; });
    cnt = sum = 0;
    dsu.init(n);
    for (int now = 0, i = 1; i <= m && now < n - 1; i++)
    {
        auto [u, v, w, c] = e[i];
        if (dsu.qry(u, v)) continue;
        dsu.merge(u, v), now++, cnt += !c, sum += w;
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for (int u, v, w, c, i = 1; i <= m; i++) cin >> u >> v >> w >> c, (c ? e1[++m1] : e2[++m2]) = {u + 1, v + 1, w, c};
    sort(e1 + 1, e1 + 1 + m1, [](edge x, edge y)
         { return x.w < y.w; });
    sort(e2 + 1, e2 + 1 + m2, [](edge x, edge y)
         { return x.w < y.w; });
    int l = -114, r = 514, mid;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        for (int i = 1; i <= m2; i++) e2[i].w -= mid;
        kruskal();
        if (cnt < k)
            l = mid + 1;
        else
            ans = sum + mid * k, r = mid - 1;
        for (int i = 1; i <= m2; i++) e2[i].w += mid;
    }
    cout << ans;
    return 0;
}

P5633 最小度限制生成树

给你一个有 \(n\) 个节点，\(m\) 条边的带权无向图，你需要求得一个生成树，使边权总和最小，且满足编号为 \(s\) 的节点正好连了 \(k\) 条边。

可能会出现无解的情况，如果无解，则输出 Impossible。

对于 \(20\%\) 的数据，\(n \le 10\)， \(m \le 30\)。 对于 \(50\%\) 的数据，\(n \le 1000\)， \(m \le 5000\)。 对于 \(100\%\) 的数据，\(1\leq s \leq n \le 5\times 10^4\)， \(1\leq m \le 5\times 10^5\)， \(1\leq k \le 100\)， \(0\leq w\leq 3\times 10^4\)。

按是否与 \(s\) 相连分组，和上面不同的是，我们要判无解，我们可以把 \(\Delta\) 设为 \(\pm \text{inf}\)，并根据此时白边数量与 \(k\) 的关系判断无解。

实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int MAXN = 1e6 + 10;
class DSU
{
    int f[MAXN];
    int getf(const int x) { return f[x] = (f[x] == x ? x : getf(f[x])); }

public:
    void init(int n)
    {
        for (int i = 1; i <= n; i++) f[i] = i;
    }
    bool qry(const int x, const int y) { return getf(x) == getf(y); }
    void merge(int x, int y) { x = getf(x), y = getf(y), f[y] = x; }
} dsu;
struct edge
{
    int u, v, w, c;
} e[MAXN], e1[MAXN], e2[MAXN]; // e2 m2 -> c = 0
int ans, n, m, s, k, cnt, sum, m1, m2;
void kruskal()
{
    merge(e1 + 1, e1 + 1 + m1, e2 + 1, e2 + 1 + m2, e + 1, [](edge x, edge y)
          { return x.w == y.w ? x.c < y.c : x.w < y.w; });
    cnt = sum = 0;
    dsu.init(n);
    for (int now = 0, i = 1; i <= m && now < n - 1; i++)
    {
        auto [u, v, w, c] = e[i];
        if (dsu.qry(u, v)) continue;
        dsu.merge(u, v), now++, cnt += !c, sum += w;
    }
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> s >> k;
    for (int u, v, w, c, i = 1; i <= m; i++) cin >> u >> v >> w, ((c = !(u == s || v == s)) ? e1[++m1] : e2[++m2]) = {u, v, w, c};
    sort(e1 + 1, e1 + 1 + m1, [](edge x, edge y)
         { return x.w < y.w; });
    sort(e2 + 1, e2 + 1 + m2, [](edge x, edge y)
         { return x.w < y.w; });
    int l = -114514, r = 114514, mid;
    for (int i = 1; i <= m2; i++) e2[i].w -= r;
    kruskal();
    if (cnt < k) cout << "Impossible", exit(0);
    for (int i = 1; i <= m2; i++) e2[i].w += r;
    for (int i = 1; i <= m2; i++) e2[i].w -= l;
    kruskal();
    if (cnt > k) cout << "Impossible", exit(0);
    for (int i = 1; i <= m2; i++) e2[i].w += l;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        for (int i = 1; i <= m2; i++) e2[i].w -= mid;
        kruskal();
        if (cnt < k)
            l = mid + 1;
        else
            ans = sum + mid * k, r = mid - 1;
        for (int i = 1; i <= m2; i++) e2[i].w += mid;
    }
    cout << ans;
    return 0;
}

P4983 忘情

我们定义一段序列的值为这个：

\[\frac{\left((\sum\limits_{i=1}^{n}a_i×\bar a)+\bar a\right)^2}{\bar a^2}\]

其中 \(n\) 为此序列的元素个数。

我们给定一段长度为 \(n\) 的序列,现在要求将它分成 \(m\) 段，要求每一段的值的总和最小，求出这个最小值。

• 对于 \(30 \%\) 的数据，\(m≤n≤500\)；
• 另有 \(20 \%\) 的数据，保证 \(m=2\)；
• 对于 \(100 \%\) 的数据，\(m≤n≤100000\)， \(1≤a_i≤1000\)。

题中那个鬼式子可以化成 \((\sum a_i + 1)^2\)。

显然可用wqs二分，先不管 \(m\) 而是手动加一个额外代价 \(\Delta\)，我们设状态 \(f_i\) 为划分到 \(i\) 时的结果，记 \(s_i = \sum_{j = 1}^i a_j\)，我们有转移方程：

\[f_i = \min_{j = 0}^{i - 1} \{f_j + (s_i - s_j + 1)^2 + \Delta\}\]

这显然可以利用 斜率优化 来加速，我们把式子改写为

\[f_i - \Delta - (s_i + 1)^2 = \min_{j = 0}^{i - 1} \{f_j + {s_j}^2 - 2(s_i + 1)s_j\}\]

对比 \(b_i = \min_{j = 0}^{i - 1} \{y_j - k_ix_j\}\)，取 \(\begin{cases} k_i = 2(s_i + 1) \\ b_i = f_i - \Delta - (s_i + 1)^2 \\ x_j = s_j \\ y_j = f_j + {s_j}^2 \end{cases}\) 即可。

实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef long double ld;
const int MAXN = 1e5 + 10;
int n, m, g[MAXN], q[MAXN], hd, tl;
ll f[MAXN], s[MAXN], ans;
#define X(i) ld(s[i])
#define Y(i) ld(f[i] + s[i] * s[i])
#define K(i) ld((s[i] + 1) * 2)
ld slope(const int i, const int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
void dp(ll dta) // add dta to each cost
{
    q[hd = tl = 0] = g[0] = 0, memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
    {
        while (hd < tl && slope(q[hd], q[hd + 1]) < K(i)) hd++;
        f[i] = f[q[hd]] + (s[i] - s[q[hd]] + 1) * (s[i] - s[q[hd]] + 1) + dta, g[i] = g[q[hd]] + 1;
        while (hd < tl && slope(q[tl - 1], q[tl]) > slope(q[tl], i)) tl--;
        q[++tl] = i;
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];
    ll l = 0, r = 1e16, mid;
    while (l <= r)
    {
        dp(mid = (l + r) >> 1);
        if (g[n] <= m)
            ans = f[n] - mid * m, r = mid - 1;
        else
            l = mid + 1;
    }
    cout << ans;
    return 0;
}

P4383 [八省联考 2018] 林克卡特树

小 L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。

游戏中有一个叫做 LCT 的挑战，它的规则是这样子的：现在有一个 \(N\) 个点的树，每条边有一个整数边权 \(v_i\)，若 \(v_i \geq 0\)，表示走这条边会获得 \(v_i\) 的收益；若 \(v_i \lt 0\) ，则表示走这条边需要支付 \(-v_i\) 的过路费。小 L 需要控制主角 Link 切掉（Cut）树上的恰好 \(K\) 条边，然后再连接 \(K\) 条边权为 0 的边，得到一棵新的树。接着，他会选择树上的两个点 \(p,q\)，并沿着树上连接这两点的简单路径从 \(p\) 走到 \(q\)，并为经过的每条边支付过路费/ 获取相应收益。

海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link，如果 Link 能切掉合适的边、选择合适的路径从而使 总收益 - 总过路费 最大化的话，就把传说中的大师之剑送给他。

小 L 想得到大师之剑，于是他找到了你来帮忙，请你告诉他，Link 能得到的 总收益 - 总过路费 最大是多少。

对于全部的测试数据，保证 \(1 \leq N \leq 3 \times 10^5\)， \(0 \leq K \leq 3 \times 10^5\)， \(K \lt N\)， \(1 \leq x_i,y_i \leq N\)， \(|v_i| \leq 10^6\)。

首先先做一个转化：

给你一棵树，割掉恰好 \(k\) 条边然后重新接上恰好 \(k\) 条 \(0\) 权边，然后要求最大化新树的直径。

割掉 \(k\) 条边之后会出现 \((k+1)\) 个联通块，那么我们对于每一个联通块求直径然后用 \(k\) 条边将这 \(k\) 个联通块串起来即可了。

所以问题变成了在树上寻找 \((k+1)\) 条点不相交链，并且最大化这 \((k+1)\) 条链的边权之和。

考虑 DP，设 \(f_u\) 为链在 \(u\) 及其子树内的答案，我们发现这样难以维护路径形态，考虑到一条链上的每个节点的度数 \(d \in \{0, 1, 2\}\)，因此我们给状态再加一维 \(d\)，变成 \(f_{u, d}\) 就好转移了。

可以分类讨论出如下转移：

首先，我们约定在每个节点的全部转移结束时，进行一次更新：

\[f_{u, 0} = \max\{f_{u, 0}, f_{u, 1} + \Delta, f_{u, 2}\}\]

这样，我们就把 \(i\) 节点的全部最优解统计了出来。对于度数为 \(0/2\) 的情况可以直接合并，并对于度数为 \(1\) 的情况，要先在 \(i\) 节点处把当前 \(i\) 节点拖着的一条链断掉，然后将这条链计入总数，合并。

\[f_{u, 0} = \max\{f_{u, 0}, f_{u, 0} + f_{v, 0}\}\]

显然，如果当前节点的度数为 \(0\)，肯定不能连边，只能取子节点的最优解。

\[f_{u, 1} = \max\{f_{u, 1}, f_{u, 1} + f_{v, 0}, f_{u, 0} + f_{v, 1} + w_{u, v}\}\]

如果要求度数为 \(1\)，可以继承之前的结果，不连边。同样，可以连上这条边，继承子节点拖着的一条未完成的链，同时取这条边的权值。

\[f_{u, 2} = \max\{f_{u, 2}, f_{u, 2} + f_{v, 0}, f_{u, 1} + f_{v, 1} + w_{u, v} + \Delta\}\]

要求度数为 \(2\)，同样可以继承之前的结果，取子节点的最优解。也可以将之前 \(i\) 节点挂着的链与子节点挂着的链连接起来，就新完成了一条链。

然后就没有了。

实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int MAXN = 3e5 + 10;
int n, m, head[MAXN], k;
ll ans;
template <class T>
inline void chkmx(T &a, T b)
{
    a = a < b ? b : a;
}
struct node
{
    ll val;
    int now;
    friend bool operator<(node a, node b) { return a.val == b.val ? a.now > b.now : a.val < b.val; }
    friend node operator+(node a, node b) { return {a.val + b.val, a.now + b.now}; }
    friend node operator+(node a, ll b) { return {a.val + b, a.now}; }
} f[MAXN][3];
struct edge
{
    int v;
    ll w;
    int nxt;
} e[MAXN << 1];
void addedge(int u, int v, ll w)
{
    static int edgecnt = 0;
    e[++edgecnt] = {v, w, head[u]};
    head[u] = edgecnt;
}
void dfs(int u, int fa, node dta)
{
    f[u][0] = f[u][1] = f[u][2] = {};
    chkmx(f[u][2], dta);
    for (int i = head[u]; i; i = e[i].nxt)
    {
        auto [v, w, _] = e[i];
        if (v == fa) continue;
        dfs(v, u, dta);
        chkmx(f[u][2], max(f[u][2] + f[v][0], f[u][1] + f[v][1] + w + dta));
        chkmx(f[u][1], max(f[u][1] + f[v][0], f[u][0] + f[v][1] + w));
        chkmx(f[u][0], f[u][0] + f[v][0]);
    }
    chkmx(f[u][0], max(f[u][1] + dta, f[u][2]));
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k, k++;
    for (int u, v, w, i = 1; i < n; i++) cin >> u >> v >> w, addedge(u, v, w), addedge(v, u, w);
    ll l = -1e12, r = 1e12, mid;
    while (l <= r)
    {
        dfs(1, 1, {mid = l + r >> 1, 1});
        if (f[1][0].now <= k)
            ans = f[1][0].val - k * mid, l = mid + 1;
        else
            r = mid - 1;
    }
    cout << ans;
    return 0;
}