wqs 二分入门

MafuyuQWQ · 2025-04-11 19:59:25 · 算法·理论

简介

wqs 二分是由王钦石提出的一种解决一类有凸性问题的算法。

应用

一般可以用 wqs 二分的题目都有一个很明显的特点，就是在选取 k 个物品的限制下，求最大 / 最小值。

而且，你可以发现能用 wqs 二分的题目，令选的物品个数 cnt 为 x，以及对应的答案为 y。可得函数图像是有凸性的。

wqs 二分一般与 DP 问题的优化有关。

引入

P2619 [国家集训队] Tree I

题意：求一棵恰好包含 need 条白色边的最小生成树，并输出其边权和。

这是一道典型的 wqs 二分题，没有涉及到 DP，所以较好写。

限制为 need 条白色边，于是我们考虑选择边数 x 与其对应答案 f(x) 的关系。

设有 x_1,x_2 = x_1+1,x_3 = x_2+1，以及它们对应的答案 f(x_1),f(x_2),f(x_3)，且 f(x_1) < f(x_2),f(x_2) > f(x_3)。

也就是说这时我们增加了一条边使得选择的边数从 x_1 增加到了 x_2，且最优答案只能变大，而之后再多选一条边时，最优答案却又变小，显然我们一定会在将选择边数从 x_1 变为 x_2 时，就将最优答案减小。因此这就与假设矛盾了，可以得到 (x,f(x)) 的图像一定是下凸的。

于是考虑取一条直线 y=kx+b 去切这个凸包。切点是我们可以通过一定方法求出的，当切点为 (m,f(m)) 时，我们求出切点，就知道了最终答案。

而每次求出切点时，我们知道横坐标，所以通过二分斜率，可以很快地找到当切点为 (m,f(m)) 时的斜率。

然后，我们要考虑如何快速求出切点。

对于每个点来说，当直线经过它时，截距 b 就为 f(x)-kx，因为当直线与下凸包相切时，截距一定是最小的。所以我们需要求出截距最小的点在哪即可。

而截距的表达式是有一定意义的，就是我们每选一条白色边，就对应再添上一个 -k 的代价，这也是 wqs 二分又叫代权二分的原因（网上写法有“带” 和“代” 两种，不过我觉得后者更符合些）。

那么求截距的过程就转化为了将所有白色边加上 k 的额外代价时的最小生成树，这个不难实现。

但是有一个点，就是我们不知道这个图像是单增还是单减的，所以在二分斜率时就只能在 [-127,127] 间二分（上下界绝对值大于 100 即可）。

code

#include <bits/stdc++.h>

using namespace std;

const int N = 50010, M = 100010;

int n, m, K;
struct sb
{
    int a, b, c;
    int id;
    bool operator < (const sb &W) const
    {
        if (c != W.c) return c < W.c;
        return id < W.id;
    }
} edge[M];
int p[N], w;

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

int check(int c)
{
    w = 0;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 1; i <= m; i ++ )
        if (!edge[i].id)
            edge[i].c += c;
    sort(edge + 1, edge + 1 + m);
    int cnt = n - 1, ct = 0;
    for (int i = 1; i <= m; i ++ )
    {
        int fa = find(edge[i].a), fb = find(edge[i].b);
        if (fa == fb) continue;
        cnt -- ;
        p[fa] = fb;
        w += edge[i].c;
        ct += (bool)(!edge[i].id);
        if (!cnt) break;
    }
    for (int i = 1; i <= m; i ++ )
        if (!edge[i].id)
            edge[i].c -= c;
    return ct;
}

signed main()
{
    cin >> n >> m >> K;
    for (int i = 1; i <= m; i ++ )
    {
        cin >> edge[i].a >> edge[i].b >> edge[i].c;
        cin >> edge[i].id;
        edge[i].a ++ , edge[i].b ++ ;
    } 

    int l = -127, r = 127, res = 0;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid) >= K) res = mid, l = mid + 1;
        else r = mid - 1;
    }

    check(res);

    cout << w - K * res << '\n'; //注意最后，w是截距

    return 0;
}

接下来是第二道例题，涉及到了斜率优化 DP 的 wqs 二分优化 DP。

P4983 忘情

题意：将长度为 n 的序列分为 m 段，每段的权值为 (\sum_{i=l}^{r}a_{i}+1)^2，求使总权值和最小的最优划分方案权值和。

暴力思路就是设 f_{i,j} 表示前 i 个数，分为 j 段的最优划分方案权值和。

不难得到转移方程如下：

f_{i,j}=\min_{k=0}^{i-1}f_{k,j-1}+(S_{i}-S_{k}+1)^2

这个式子即使加上斜率优化，也不是很快，会 T。

考虑 (x, f(x)) 的图像，不难发现这一定是一个单减的下凸图像。

证明的话，就是 (a+b)^2 \ge a^2+b^2，所以分的段数越多，答案就会越小。然后注意到，这两个值的差为 2ab，也就是说在分的段数越来越多时，随着 a,b 的减小，答案减小的会越来越慢，所以这是一个下凸的图像。

然后就到了二分斜率环节。

同样地，我们将每个点表示成 (x,kx+b)，b=f(x)-kx，我们又要找出截距最小的点，每多划分一段的代价也多出 -k。

不过这次，确定是单减的图像，所以一定是用负斜率的直线去切了。

而为了方便二分，我们将 k 取一下相反数，那么代价就变为 k，二分中增大减小区间端点的操作就要反一下了。

接下来重点就是斜率优化 DP 了，因为是求切点，所以相当于说我们不考虑段数限制，只求出最终答案最小的划分段数即可。

相似地，设 f_{i} 表示前 i 个数，划分成若干段的最优答案。

状态转移方程即为：

f_i=\min_{k=0}^{i-1}f_k+(S_i-S_k+1)^2

显然，这可以用斜率优化。

化完之后的式子为：

f_i = f_i + S_i^2 + S_j^2 + 1 - 2S_iS_j - 2S_j + 2S_i + k

变换一下即为：

f_j+S_j^2 = 2(S_i+1) S_j +f_i-S_i^2-2S_i-k-1

其中 y=f_j+S_j^2,k=2(S_i+1),x=S_j,b=f_i-S_i^2-2S_i-k-1。

显然，k 是单调递增的，于是我们就可以用单调队列做。

这里维护的应该是下凸包，于是求截距就解决了。

code

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 100010, inf = 1e18;

int n, m;
int a[N], q[N];
int f[N], g[N];

// f[i] = f[j] + s[i]^2 + s[j]^2 + 1 - 2s[i]s[j] - 2s[j] + 2s[i] + K
// f[j]+s[j]^2 = 2(s[i]+1) s[j] +f[i]-s[i]^2-2s[i]-K-1
// k递增，要求截距min，故为下凸壳。 

int calc(int i)
{
    return f[i] + a[i] * a[i];
}

int check(int K)
{
    //斜率优化DP
    memset(f, 0x3f, sizeof f);
    int hh = 1, tt = 1;
    f[0] = g[0] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        while (hh < tt && calc(q[hh + 1]) - calc(q[hh]) < (a[q[hh + 1]] - a[q[hh]]) * 2ll * (a[i] + 1)) hh ++ ;
        int j = q[hh];
        f[i] = f[j] + (a[i] - a[j] + 1) * (a[i] - a[j] + 1) + K;
        g[i] = g[j] + 1;
        while (hh < tt && (double)(calc(q[tt]) - calc(q[tt - 1])) * (a[i] - a[q[tt - 1]]) > (double)(calc(i) - calc(q[tt - 1])) * (a[q[tt]] - a[q[tt - 1]])) tt -- ;
        q[ ++ tt] = i;
    }

    return g[n];
}

signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], a[i] += a[i - 1];

    int l = 0, r = inf, res = 0;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid) <= m) res = mid, r = mid - 1;
        else l = mid + 1;
    }

    check(res);

    cout << f[n] - res * m << '\n';

    return 0;
}

注意点

关于 wqs 二分

二分区间。二分区间我们应该先判断答案的凸性以及增减性，然后再判断去切这个凸包的斜率应为正或负。这个比较好判断。
二分中更新答案斜率的方式，也就是写
```
if(check(mid)<=m) res=mid...
```
还是写
```
if(check(mid)>=m) res=mid...
```
的问题，这个一般是取决于写法的。如果说在求截距的过程中，有两种选法答案相同时，你选择选取物品个数较少的方案更新的话，那么上面就应该是小于等于；反之大于等于。因为有物品个数增多且答案不变的方案就说明，即使你二分出来的切点横坐标是小于 m 的，你也可以通过多选或替换后再多选一些对答案无影响的物品，使得选择物品个数达到 m。在图像上来看，就是这个斜率的直线与凸包上的一段点重合。
若是用 wqs 二分优化斜率优化 DP 的话，在找切点时，判断条件要看下方 wqs 二分中的写法。当判断条件中两边相等时，说明直线与凸包某一段重合，根据二分中写法考虑是尽量少取或多取，少取的话应该是不能加等号的。

关于斜率优化 DP

在判断维护上凸包或下凸包时，应该是看维护最大值 or 最小值的，具体证明不会，不过我猜想是因为切上凸包时，不管斜率正负，截距都是最大的，所以维护最大值的 DP，要维护上凸包；反之则是下凸包。
判断是否能直接单调队列维护到 O(n) 时，应该看式子中的 k 是否单增或单降。

习题

P3620 [APIO/CTSC2007] 数据备份

注意到一个性质，连相邻的点一定是要优于中间跨过了点的方案的，所以就是最大独立集。

感性理解。

二分斜率，对每一条连的边增加代价，求截距改为不考虑条数限制的状态机 DP（最大独立集）即可。

code

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 100010;

int n, k;
int a[N];
int f[N][2], g[N][2];

int check(int K)
{
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    g[1][0] = g[1][1] = 0;
    for (int i = 2; i <= n; i ++ )
    {
        if ((f[i - 1][1] < f[i - 1][0]) || (f[i - 1][1] == f[i - 1][0] && g[i - 1][1] < g[i - 1][0])) 
            f[i][0] = f[i - 1][1], g[i][0] = g[i - 1][1];
        else f[i][0] = f[i - 1][0], g[i][0] = g[i - 1][0];
        f[i][1] = f[i - 1][0] + a[i] - a[i - 1] - K, g[i][1] = g[i - 1][0] + 1;
    }

    if (f[n][0] > f[n][1] || (f[n][0] == f[n][1] && g[n][1] < g[n][0])) return g[n][1];
    else return g[n][0];
}

signed main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    int l = 0, r = 2e9, res = 0; 
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid) <= k) res = mid, l = mid + 1;
        else r = mid - 1;
    } 
    check(res);

    cout << min(f[n][0], f[n][1]) + k * res << '\n';

    return 0;
}

P5308 [COCI 2018/2019 #4] Akvizna

大部分题解都是反着做的，不过正着做也是可以的，可能有精度问题什么的，反正过了，也无所谓了。

设 f_{i,j} 表示考虑到第 i 个人时，过了 j 轮的最大奖金。

f_{i,j}=\max_{k=0}^{i-1}(f_{k,j-1}+\frac{i-k}{n-k})

二分斜率，求截距变为设 f_i 表示到第 i 个人时，进行了若干轮后的最大奖金。

f_i=\max_{j=0}^{i-1}(f_{j}+\frac{i-j}{n-j})

典型斜率优化 DP。

f_i=f_j+\frac{i-j}{n-j}

f_j-\frac{j}{n-j}=(-i) \times \frac{1}{n-j}+f_i

则 y=f_j-\frac{j}{n-j},k=-i,x=\frac{1}{n-j},b=f_i。

然后上斜率优化，因为是最大值，所以应该是上凸包。

注意到 k 单调递减，且为负数，所以单调队列时把凸包上边斜率大于 k 的都弹掉即可。

code

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, inf = 1e9;
const double eps = 1e-12;

int n, k, q[N];
double f[N];
int g[N];

/*
nf[j]-jf[j]=n-i-n+j+nf[i]-jf[i]
nf[j]-jf[j]=(1-f[i])j+nf[i]-i
f[i]=f[j]+(i-j)/(n-j)

f[j]-j/(n-j)=f[i]+(-i)*1/(n-j)
k单降，为负

(x,f[x])
*/

double X(int i, int j)
{
    return (1.0 / (n - i) - 1.0 / (n - j));
}

double Y(int i, int j)
{
    return (f[i] - i * 1.0 / (n - i) - f[j] + j * 1.0 / (n - j));
}

double calc(int i, int j)
{
    return Y(i, j) / X(i, j);
}

int check(double K)
{
    memset(f, 0x3f, sizeof f);
    f[0] = g[0] = 0;
    int hh = 1, tt = 1; 
    for (int i = 1; i <= n; i ++ )
    {
        while (hh < tt && calc(q[hh + 1], q[hh]) > (-i)) hh ++ ;
        int j = q[hh];
        f[i] = f[j] + (i - j) * 1.0 / (double)(n - j) - K;
        g[i] = g[j] + 1;
        while (hh < tt && calc(q[tt], q[tt - 1]) < calc(i, q[tt - 1])) tt -- ;
        q[ ++ tt] = i;
    }

    return g[n];
}

signed main()
{
    cin >> n >> k;

    double l = 0, r = inf * 1.0, res = 0;
    while (r - l >= eps)
    {
        double mid = (l + r) * 0.5;
        if (check(mid) <= k) res = r = mid;
        else l = mid; 
    }

    check(res);

    printf("%.9lf\n", f[n] + res * k); 

    return 0;
}