WQS二分—简介及基本应用

WQS二分是啥？搞了这么久我连它的全名是什么都一头雾水，姑且称其为忘情水二分吧。
先推荐一个博客 https://www.cnblogs.com/CreeperLKF/p/9045491.html
再来膜一个dalao https://www.cnblogs.com/AKCqhzdy/

理论

忘情水二分的模型：给出一些选物品的条件，不同的组合法会有不同的价值，要求刚好选m个，最大化（最小化）总价值。
设选x个物品时的最优价值为g(x)，以x为横坐标，价值为纵坐标，那么g(x)会呈现出一个上凸包的形状。
我们要求得显然是g(m)，但是并不好直接求，因为这个形状我们只是大概知道而已。
那么考虑构造一些直线来切这个凸包，从而求出这个凸包的形状，进而找到g(m)的值。
我们枚举一条斜率为mid的直线通过一次O（N）的求解，可以找到这条直线的最高位置g(x)，即找到恰好相切的截距。在求解过程中我们还可以顺便得到x，也就是说我们得到了凸壳上的一个点(x,g(x))。
关键不在于这个g(x)，而在于x。这个x如果是小于m的，那么我们要考虑下次枚举时加大x，也就是说要加大斜率；同理，如果x大于了m，那么就要使下一次枚举的x变小，就是要减小斜率。相当于问题就是找到一个直线的斜率，使得这条直线与凸包的切点横坐标为x。横坐标很显然满足二分性，同样的，因为凸包的斜率单调递减，即斜率也是可以二分的。这两个都满足二分性，所以最终结果可以二分。
二分直到x=m时，结束二分，此时计算的ans才是真正的ans。设截距为f(x)，因为g(x)=kx+f(x)，所以f(x)=g(x)-kx，那么ans=g(x)-k*x。

例题

Ⅰ

bzoj2654 tree

这是一道最最最基础的忘情水二分了。
二分一个值mid，白边所有白边加上mid之后做一个最小生成树，注意统计最小生成树中白边的条数tot和最小生成树的边权和sum。这个tot相当于x，sum相当于g(x)。所以当x大于need是减小斜率，注意考虑斜率与mid的关系（mid越大，选的白边越少，也就是斜率越小），实际上是要增大mid；反之同理。
在考虑一个细节，如果当x=x0时，白边数大于need，但x=x0+1时白边数小于need，这说明有在x=x0时，有很多白边与黑边的权值相同，此时应当减少一下白边数量。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=1<<30;
const int MAXN=50010,MAXM=100010;
 
int v,e,need;
 
struct E{int x,y,v,c;}a[MAXM];
bool cmp(E a1,E a2)
{
    if(a1.v!=a2.v) return a1.v<a2.v;
    return a1.c<a2.c;//debug
}
 
int fa[MAXN];
int findfa(int x){return x==fa[x]?fa[x]:findfa(fa[x]);}
 
int mintree;
int kruskal(int mid)
{
    for(int i=1;i<=e;i++) if(a[i].c==0) a[i].v+=mid;
    for(int i=1;i<=v;i++) fa[i]=i;
    sort(a+1,a+e+1,cmp);//debug
    mintree=0;int re=0;
    for(int i=1,cnt=1;i<=e;i++)
    {
        int fx=findfa(a[i].x),fy=findfa(a[i].y);
        if(fx!=fy)
        {
            fa[fx]=fy;
            mintree+=a[i].v;
            if(a[i].c==0) re++;
            cnt++;if(cnt==v) break;
        }
    }
    for(int i=1;i<=e;i++) if(a[i].c==0) a[i].v-=mid;
    return re;
}
 
int main()
{
    scanf("%d%d%d",&v,&e,&need);
    for(int i=1;i<=e;i++) scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].v,&a[i].c),a[i].x++,a[i].y++;
     
    int l=-105,r=105,ans;//???
    while(l<=r)
    {
        int mid=l+r>>1;
        if(kruskal(mid)>=need) ans=mintree-mid*need,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

下面两篇没有那么模板了，我们另外来讲。

Ⅱ

bzoj5311 贞鱼 题解链接

Ⅲ

洛谷T51924 忘情 题解链接

总结

WQS二分一般是用来优化那种斜率满足递减性的DP，如果同时在不要求满足说要选多少个时能够比较快的的求出一个结果，还可以降维的话，那么WQS二分就是一个优选。