Wqs二分小结

, ,

wqs 二分小结

简介

wqs二分 是神仙 王钦石 在 2012 年论文中提出的一类二分方式。
基本是用来处理一类带有限制的问题的。比较明显的标志就是 恰好选 K 个 等。
使用 wqs二分 有一个前提：原问题具有凹凸性。

举个例子，比如我们的函数是上凸的。

那么根据定义，它的斜率肯定单调递减。

于是，我们可以二分这个斜率，然后快速算出它切这个凸包会切在哪里。

对于点 $(x,F(x))$，其实际意义在于恰好选 $x$ 个，其最大价值为 $F(x)$。二分求的是斜率的截距最小的。令二分的斜率为 $k$。

截距 $b=F(x)-x\times k$，由于恰好选 $x$ 个，$-k$ 可以减到所有点的权值上。那么二分这个斜率的实际意义为，每个权值减去 $-k$ 之后，找到这个斜率下在凸包上最优是哪个点，也就是恰好选几个。只需要在每次二分判断的时候记录最优的时候选了几个。

一些小问题

考虑三点共线的情况。所以每次二分权值的时候，强制令相同优的情况下，选择最多/最少的个数。我习惯于选择最多的个数，实现看代码。

其实我自己都不知道我在讲什么，还是 zj 哥哥手把手教的更好。

例题

1. [国家集训队] Tree I

https://www.luogu.com.cn/problem/P2619

为了满足最多的情况，强制在权值相同时，优先选择白边。复杂度 $O(n\log^2 n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 100005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,m,K;
int fa[maxn];
struct yyy{
	int x,y,z,c;
}e[maxn],a[maxn];
inline bool cmp(yyy x,yyy y) {return x.z==y.z?x.c<y.c:x.z<y.z;}
int Value,ans=1e9;
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
inline int Kruskal(int val) {
	int i,sum=0;Value=0;
	for (i=1;i<=n;i++) fa[i]=i;
	for (i=1;i<=m;i++) 
		if (e[i].c) a[i]=e[i];
		else a[i]=e[i],a[i].z+=val;
	sort(a+1,a+1+m,cmp);
	for (i=1;i<=m;i++) {
		if (getfa(a[i].x)^getfa(a[i].y)) {
			fa[getfa(a[i].x)]=getfa(a[i].y);
			Value+=a[i].z;
			sum+=(a[i].c==0);
		}
	}
	return sum;
}
signed main(void){
	int i,x,y,z;
	read(n);read(m);read(K);
	for (i=1;i<=m;i++) {
		read(e[i].x),read(e[i].y),read(e[i].z),read(e[i].c);
		e[i].x++,e[i].y++;
	}
	int l=-101,r=101;
	while (l+1<r) {
		int mid=l+r>>1;
		if (Kruskal(mid)>=K) l=mid,ans=Value-K*mid;//因为不一定二分到恰好选 k 个的情况，所以记录答案
		else r=m
	}
	printf("%d",ans);
	return 0;
}

但是观察到白边和黑边各自内部中的相对顺序并不会改变。可以提前排序两部分，后归并。复杂度就是 $O(n\log n)$。

2. 最小度限制生成树

https://www.luogu.com.cn/problem/P5633

优先选择与 $s$ 相邻的点。

3. CF125E MST Company

双倍经验。

4. CF802O April Fools’ Problem (hard)

先判断是否有凸性。

二分之后，考虑反悔贪心。有两种情况：

  • 从之前没配对 $a_x$ 中选一个，代价是 $b_i+a_x$。
  • 从之前的已经组成的 $(a_x,b_y)$ 拆掉，代价是 $b_i-b_y$

强制权值最大的同时选的最多。复杂度 $O(n\log^2 n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define int long long
#define maxn 500005
#define fi first
#define se second
#define mk make_pair
int n,K;
const int inf=2e9;
int a[maxn],b[maxn],c[maxn];
priority_queue<pair<int,int> >q;
int Ans,sum,ans;
inline bool check(int val) {
	int i;Ans=0,sum=0;
	while (!q.empty()) q.pop();
	for (i=1;i<=n;i++) c[i]=b[i]-val;
	for (i=1;i<=n;i++) {
		q.push(mk(-a[i],1));
		if (-q.top().fi+c[i]<=0) {
			sum+=q.top().se;
			Ans+=c[i]-q.top().fi;
			q.pop();
			q.push(mk(c[i],0));
		}
	}
	return sum>=K;
}
signed main(void){
	int i;
	read(n);read(K);
	for (i=1;i<=n;i++) read(a[i]);
	for (i=1;i<=n;i++) read(b[i]);
	int l=-inf,r=inf,mid;
	while (l+1<r) {
		mid=l+r>>1;
		if (check(mid)) r=mid,ans=Ans+mid*K;
		else l=mid;
	} 
	printf("%lld",ans);
	return 0;
}

5. P4983 忘情

6. [IOI2000] 邮局 加强版

判断时用决策单调性优化。

7. P5308 [COCI2018-2019#4] Akvizna

同上。

写在最后

感觉这篇写的水了一点。但是要退役了，就当记录一下好了。

其实也不大会有人看。