WQS 二分（又称“带权二分”或国外的 Aliens Trick）是解决“恰好选 $k$ 个”这类带有数量限制最优化问题的核心利器。它的本质是利用凸性（Convexity），通过二分斜率 $mid$ 引入惩罚/奖励权值，将原本必须记录“已选个数”的状态维度剥离，把复杂度从 $O(N \cdot K)$ 降为 $O(N \log V)$。

---

一、 核心思想与适用条件

1. 适用场景

面对如下形式的问题：

给定若干元素，要求恰好选出 $k$ 个（或分成 $k$ 段、做 $k$ 次操作），使得总代价最小（或总收益最大）。

设 $f(x)$ 为“恰好选 $x$ 个”时的最优解。如果直接做 DP，状态通常为 $dp[i][j]$ 表示前 $i$ 个选了 $j$ 个，复杂度往往在 $O(N^2)$ 或更高。

2. 前提条件：凸性

WQS 二分能使用的充要条件是函数 $f(x)$ 具有凸性：

• 求最小值：$f(x)$ 必须是下凸函数（斜率单调不减），即满足：

$$f(x+1) - f(x) \ge f(x) - f(x-1)$$

• 求最大值：$f(x)$ 必须是上凸函数（斜率单调不增），即满足：

$$f(x+1) - f(x) \le f(x) - f(x-1)$$

(注：在竞赛中，判断凸性通常有两种方式：一是通过四边形不等式或费用流凸性严格证明；二是打表观察前几项差分是否单调。)

---

二、 几何直观与算法流程

以求最小值（下凸函数）为例，把点集 $(x, f(x))$ 画在平面直角坐标系上，它们会构成一个向下凸的壳（凸包）。

1. 切线变换（引入惩罚 $mid$）

想象一条斜率为 $mid$ 的直线 $y = mid \cdot x + b$ 从下方去切这个凸包，截距为：

$$b = f(x) - mid \cdot x$$

要使直线切到凸包，截距 $b$ 必须最小。 观察表达式 $f(x) - mid \cdot x$：它的物理意义是“每多选一个物品，额外付出 $mid$ 的代价（当 $mid < 0$ 时即为获得 $\vert{}mid\vert{}$ 的奖励）”。

去掉“恰好选 $k$ 个”的限制后，我们只需在不限制数量的前提下，求解带权新问题的最小代价：

$$g(mid) = \min_{x} \{ f(x) - mid \cdot x \}$$

2. 二分斜率与还原答案

因为 $f(x)$ 下凸，斜率 $mid$ 越大，切点横坐标 $x$ 越小（选得越少）；斜率 $mid$ 越小，切点横坐标 $x$ 越大（选得越多）。因此 $x$ 关于 $mid$ 具有单调性！

1. 二分斜率 $mid$。
2. 在无数量限制下求出最优值 $g(mid)$，并顺便记录达到最优值时选了多少个（记为 $cnt$）。
3. 若 $cnt \ge k$，说明当前惩罚不够（或奖励太多），可以记录当前合法候选答案 $ans = g(mid) + k \cdot mid$，并调大 $mid$；否则调小 $mid$。

---

三、 最关键的细节：三点共线（平局处理）

实战中，凸包上经常出现连续多个点斜率相同的情况，即存在 $x_1 < k < x_2$ 使得：

$$f(x_1) - mid \cdot x_1 = f(k) - mid \cdot k = f(x_2) - mid \cdot x_2 = g(mid)$$

此时，无限制求解 $g(mid)$ 时，不同的转移顺序可能会算出 $cnt = x_1$，也可能算出 $cnt = x_2$。如果代码处理不统一，二分边界就会出错！

黄金法则：强制偏向同一侧

• 策略（推荐）：在代价相同时，尽量多选（即取 $x_2$）。
• 对应二分条件：当 $cnt \ge k$ 时，更新 ans = g(mid) + k * mid，并尝试增大惩罚（求最小值时 l = mid + 1，求最大值时 r = mid - 1）。
• 为什么即使 $cnt = x_2 > k$ 也能用 g(mid) + k * mid 更新答案？ 因为 $(k, f(k))$ 就在这条斜率为 $mid$ 的直线上！既然直线的截距是 $g(mid)$，那么 $f(k) - mid \cdot k = g(mid)$ 必然严格成立，移项即得 $f(k) = g(mid) + k \cdot mid$。

---

四、 典型例题解析

例题 1：最小生成树变形 —— 洛谷 P2619 [国家集训队] Tree I

题意简述

给你一个无向带权连通图，每条边是黑色或白色。要求找一棵恰好有 $need$ 条白边的最小生成树，输出最小权值和。

思路分析

1. 凸性判断：白边选得越多，不得不选入劣质白边的概率越大，边权和的增量单调不减，因此 $f(x)$ 是下凸函数。
2. 剥离限制：给所有白边的边权加上一个偏移量 $mid$（$mid$ 可正可负）。每多选一条白边，总代价就增加 $mid$。
3. 三点共线处理：在 Kruskal 排序时，如果一条白边（改权后）和一条黑边权值相同，为了尽量多选白边，规定白边排在黑边前面。
4. 二分范围：边权在 $[1, 100]$ 之间，因此 $mid$ 的二分范围设为 $[-105, 105]$ 即可覆盖所有情况。

参考代码（C++）

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v, w, col; // col = 0 为白边, 1 为黑边
    int real_w;
};

int n, m, need;
vector<Edge> edges;
int fa[50005];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

// 检查当白边附加权值为 mid 时，最少/最多能选多少条白边
pair<int, int> check(int mid) {
    for (int i = 0; i < n; i++) fa[i] = i;
    for (auto &e : edges) {
        e.real_w = e.w + (e.col == 0 ? mid : 0);
    }
    // 关键：权值相同时，白边 (col=0) 优先，实现“尽量多选”
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
        if (a.real_w != b.real_w) return a.real_w < b.real_w;
        return a.col < b.col;
    });

    int sum = 0, white_cnt = 0;
    for (const auto &e : edges) {
        int fu = find(e.u), fv = find(e.v);
        if (fu != fv) {
            fa[fu] = fv;
            sum += e.real_w;
            if (e.col == 0) white_cnt++;
        }
    }
    return {white_cnt, sum};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> need;
    edges.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w >> edges[i].col;
    }

    int l = -105, r = 105, ans = 0;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        auto [cnt, sum] = check(mid);
        if (cnt >= need) {
            // 合法候选：减去多算的 need * mid
            ans = sum - need * mid;
            l = mid + 1; // 增加白边惩罚，减少白边数量
        } else {
            r = mid - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

---

例题 2：序列分段 + 斜率优化 —— 洛谷 P4983 忘情

题意简述

给定长度为 $n$ 的正整数序列 $x_1, x_2, \dots, x_n$，将其分成恰好 $m$ 段。设某一段元素和为 $S$，则该段代价为 $(S + 1)^2$。求最小总代价。

思路分析

1. 凸性判断：设区间代价 $w(l, r) = (pre_r - pre_{l-1} + 1)^2$。由于二次函数导数递增，$w(l, r)$ 满足四边形不等式，因此分 $m$ 段的最小代价函数 $f(m)$ 严格下凸。
2. 剥离段数限制：每分出一段，额外加上惩罚 $mid$。转移方程变为一维：

$$dp[i] = \min_{0 \le j < i} \{ dp[j] + (pre_i - pre_j + 1)^2 + mid \}$$

3. 斜率优化加速：展开平方项并移项（令 $s_i = pre_i$）：

$$\underbrace{(dp[j] + s_j^2 - 2s_j)}_{Y_j} = \underbrace{2s_i}_{K_i} \cdot \underbrace{s_j}_{X_j} + \underbrace{(dp[i] - s_i^2 - 2s_i - 1 - mid)}_{B_i}$$

横坐标 $s_j$ 严格递增，斜率 $2s_i$ 严格递增，直接用单调队列维护下凸壳，$O(n)$ 即可完成一次 check。 4. 三点共线处理：在单调队列弹队头时，若 slope(q[head], q[head+1]) <= 2 * s[i]（注意取等号 <=），则弹出队头，保留靠后的决策点 $j$，从而让分段数 $cnt[i] = cnt[j] + 1$ 尽量大。

参考代码（C++）

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
using i128 = __int128;

const int MAXN = 100005;
int n, m;
ll s[MAXN], dp[MAXN];
int cnt[MAXN], q[MAXN];

inline ll Y(int j) {
    return dp[j] + s[j] * s[j] - 2 * s[j];
}

inline ll X(int j) {
    return s[j];
}

// 检查分成若干段（每段附加代价 mid）的最优解
void check(ll mid) {
    int head = 1, tail = 1;
    q[1] = 0;
    dp[0] = 0;
    cnt[0] = 0;

    for (int i = 1; i <= n; i++) {
        // 关键：斜率相等时也弹出队头，选择更靠后的 j，使分段数 cnt 尽可能大
        while (head < tail && (i128)(Y(q[head + 1]) - Y(q[head])) <= (i128)2 * s[i] * (X(q[head + 1]) - X(q[head]))) {
            head++;
        }
        int j = q[head];
        ll seg = s[i] - s[j] + 1;
        dp[i] = dp[j] + seg * seg + mid;
        cnt[i] = cnt[j] + 1;

        // 维护下凸壳，斜率相等时也弹出队尾
        while (head < tail && (i128)(Y(q[tail]) - Y(q[tail - 1])) * (X(i) - X(q[tail])) >= (i128)(Y(i) - Y(q[tail])) * (X(q[tail]) - X(q[tail - 1]))) {
            tail--;
        }
        q[++tail] = i;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        s[i] = s[i - 1] + x;
    }

    ll l = 0, r = (s[n] + 1) * (s[n] + 1), ans = 0;
    while (l <= r) {
        ll mid = l + (r - l) / 2;
        check(mid);
        if (cnt[n] >= m) {
            ans = dp[n] - (ll)m * mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

---

五、 教练实战总结与避坑指南

易错点	表现症状	解决方案
二分上下界不够宽	某些极端数据下 cnt 始终达不到 k，或 ans 未更新	仔细估算最大斜率差：通常是单步最大代价增益的 $1 \sim 2$ 倍；注意某些题（如 Tree I）斜率可以为负数。
平局方向不一致	样例能过，但大数据点因为共线问题 WA	统一采用“平局时多选”模板：代价相等时优先选入（或选靠前的转移点），二分判定固定写 if (cnt >= k)。
中间变量溢出	斜率优化叉乘或总代价乘以 $mid$ 时爆 long long	斜率比较一律使用 __int128；计算 dp[n] - k * mid 前检查数量级。
忽略“至多选 $k$ 个”的情况	题目要求“至多选 $k$ 个”而非“恰好 $k$ 个”	只需先做一次 $mid = 0$ 的无限制求解，若最优数量 $cnt_0 \le k$，直接输出 $dp_0$ 即可，无需二分。