【听课笔记】带权二分(wqs二分)

这个东西大概好早就想学了,但是一直没学。这次就认真学一下吧。

基础操作

当题目给了一个选物品的限制条件,要求刚好选 $m$ 个,要求最大化/最小化权值,然后其特点就是当选的物品越多的时候权值越大(越小)。

然后大概这个凸性一般都是靠猜的

考虑去二分一个 $w$,表示选一个满足限制的物品时附加的权值,如果 $w$ 越大,那么选的物品个数就会越多/越少,权值越大/小。考虑当这个函数是凸的时候,于是当选的物品个数大于 $m$ 时,减小 $w$,否则增大 $w$,最后计算答案的时候去掉 $w$ 值的影响即可。

考虑这么做的原理。如果设 $f(x)$ 表示选了 $x$ 个满足限制的物品时的最优解。那么根据凸性,$f(x)$ 随着 $x$ 的增大,斜率单调,所以一定会是一个下凸壳或者上凸壳。但问题就在于唯一知道的信息只是其凸性,无法求出 $f(m)$ 的准确值。

考虑凸壳的一个特点。假设这个凸壳是光滑的,那么对于每个斜率 $k$ ,凸壳上一定存在一点与某条该斜率的直线相切。同时假设斜率为 $k$ 但不限制截距的直线 $l$ 与该凸壳有交时,截距的极值一定是取到 $l$ 与凸壳相切的时候。

记截距为 $b$ 。可知有 $b=f(x) - kx$ 。考虑构造这个式子中 $b$ 的含义,发现本质上等价于每选一个物品,$f(x)$ 就要减掉 $k$ ,最终选了 $x$ 个物品,总答案就要减小 $kx$ 。 所以考虑如果把所有物品的权值一开始就减掉 $k$,那么当 $f(x)$ 最大时,$b$ 也一定最大。所以此时对于某个斜率 $k$,都可以线性或者低次 $poly(\log)$ 求出 $\min\{f(x)\}$ 并且求出决策点 $x$。

考虑如何加速这个过程。发现在凸的时候,斜率 $k$ 和 $x$ 同时单调,于是考虑二分这个斜率。例如在某个斜率 $k’$ 下选择的物品 $>m$ ,那么就需要让 $x$ 变小,根据 $k$ 和 $x$ 的相对单调关系调整即可。

12年集训队胡策 Tree I

给你⼀个⽆向带权连通图,每条边是⿊⾊或⽩⾊。让你求⼀棵最⼩权的恰好有 $need$ 条⽩⾊边的⽣成树。

$1\leq n\leq 50000,1\leq m\leq 100000$ 。

发现就是 $wqs$ 二分的裸题。那么考虑直接去二分每条白边加上的权值 $w$ 即可。注意到白边无论 $w$ 是多少,选取时的单调性不变。所以可以利用这个将复杂度从 $m(\log m+\log n) \log V$ 优化到 $m\log n\log v+m\log m $。注意到并查集的 $\log $ 是极小的。

但值得注意的是,这题构造方案的话并不存在一个很简单的方法。

还有一点细节需要注意。就是假设存在某几条黑边与加权之后的白边权值相同的话,不能随便选。本质上,优先选黑边和优先选白边都一样。也就是需要规定优先选白边或者优先选黑边,但是两者的处理方式是不同的。如果优先选黑边的话,那么判的时候就要判 $\leq$ ,优先选白边则需要判 $\geq$ 。

亲测似乎优先选白边会快一点。下面是优先选黑边的代码:

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
61
62
63
64
65
const int N = 200010 ;

struct Edge{
int fr ;
int to ;
int clr ;
int val ;
int next ;
}E[N << 1] ;

int cnt ;
int ans ;
int fa[N] ;
int n, m, k ;
int head[N] ;

void add(int x, int y, int w, int c){
to(++ cnt) = y ;
nxt(cnt) = head[x] ; head[x] = cnt ;
fr(cnt) = x ; val(cnt) = w ; clr(cnt) = c ;
}
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]) ;
}
bool comp(Edge a, Edge b){
return a.val == b.val ? a.clr > b.clr : a.val < b.val ;
}
bool mst(int x){
int re = 0, ret = 0, y = 0 ;
for (int i = 1 ; i <= cnt ; ++ i)
if (!clr(i)) val(i) += x ;
for (int i = 1 ; i <= n ; ++ i) fa[i] = i ;
sort(E + 1, E + cnt + 1, comp) ;
for (int i = 1 ; i <= cnt ; ++ i){
int f1 = find(fr(i)) ;
int f2 = find(to(i)) ;
if (f1 == f2) continue ;
ret += val(i) ; fa[f1] = f2 ;
re += (clr(i) ^ 1) ; ++ y ;
if (y == n - 1) break ;
}
for (int i = 1 ; i <= cnt ; ++ i)
if (!clr(i)) val(i) -= x ;
//cout << x << " " << re << " " << ret << endl ;
if (re <= k){
ans = ret - k * x ;
return 1 ;
}
return 0 ;
}
int main(){
int u, v, w, c ;
ios:: sync_with_stdio(false) ;
cin.tie(0) ; cin >> n >> m >> k ;
for (int i = 1 ; i <= m ; ++ i)
cin >> u >> v >> w >> c, add(++ u, ++ v, w, c) ;
int l = -10000, r = 10000, mid, res ;
while (l <= r){
mid = (l + r) >> 1 ;
//cout << l << " " << r << endl ;
if (mst(mid)) r = mid - 1 ; else l = mid + 1 ;
}
//cout << res << endl ; mst(res) ;
cout.tie(0) ; cout << ans << endl ; return 0 ;
}

IOI2000 邮局

⼀条路有 $n$ 个村庄,你要建 $k$ 个邮局,每个村庄到最近邮局距离最小。

$k\leq 300,n\leq 3000$ 。

这个东西,就显然是 $f_{i,j}$ 记一下,然后放 $k\to i$ 的中点就好了。这样复杂度是 $n^2k$ 的。然后编一下发现有决策单调性,就可以 $O(nk\log n)$ 甚至 $O(nk)$ 了。

然而这个地方打算记录一下怎么 $wqs$ 做。考虑去优化一下上面那种解法,发现 $k$ 这个限制可以通过wqs二分给消掉,就变成了如果建一次邮局需要额外支付 $mid$ 的代价,但是不限制建的次数时的最短距离和。这个东西就变成了一个1D/1D的 $dp$ ,并且也具有决策单调性。这一部分就可以继续单调栈+二分做到 $n\log V\log n$

似乎有什么很优秀的单调队列做法可以做到线性。不过写了写发现似乎二分的常数还是很小的,$n=5\times 10^5$ 也只需要谷 $2.7s$ 、uoj $2s$ 左右。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <bits/stdc++.h>

using namespace std ;

const int N = 1000010 ;

//#define int long long

#define il inline

typedef long long ll ;

int tp ;
ll res ;
ll f[N] ;
ll sum[N] ;
int lrg[N] ;
int cnt[N] ;
int stk[N] ;
int base[N] ;
int n, m, k ;

namespace IPT {

const int L = 1 << 21;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) end = buf + fread(front = buf, 1, L, stdin);
return (front == end) ? -1 : *(front++);
}
template <typename T>
inline void qr(T &x) {
char ch = GetChar(), lst = x = 0;
while (!isdigit(ch)) lst = ch, ch = GetChar();
while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = GetChar();
if (lst == '-') x = -x;
}
template <typename T>
void qra(T *const __ary, int __n) {
for (int i = 1; i <= __n; ++i) qr(__ary[i]);
}
template <typename T>
int qrs(T *p) {
T *beg = p;
do *p = GetChar(); while (!isalnum(*p));
do *(++p) = GetChar(); while (isalnum(*p));
*p = 0;
return p - beg;
}
template <typename T>
void qrdb(T &x) {
char ch = GetChar(), lst = x = 0;
while (!isdigit(ch)) lst = ch, ch = GetChar();
while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = GetChar(); }
if (ch == '.') {
ch = GetChar();
for (double t = 0.1; isdigit(ch); t *= 0.1) {
x += (t * (ch - '0'));
ch = GetChar();
}
}
if (lst == '-') x = -x;
}

}

namespace OPT {

const int L = 30;
char buf[L];

template <typename T>
inline void qw(T x, const char aft = 0) {
if (x < 0) { x = -x, putchar('-'); }
int top = 0;
do { buf[++top] = static_cast<char>(x % 10 + '0'); } while (x /= 10);
while (top) putchar(buf[top--]);
if (aft) putchar(aft);
}
template <typename T>
void qwa(T *const __ary, int __n, const char e1, const char e2) {
for (int i = 1; i < __n; ++i) qw(__ary[i], e1);
qw(__ary[__n], e2);
}
template <typename T>
void qws(T *p, const int __n, const char ed) {
for (int i = 0; i < __n; ++i) putchar(p[i]);
if (ed) putchar(ed);
}
template <typename T>
void qws(T *p, const char ed) {
while (*p) putchar(*p++);
if(ed) putchar(ed);
}

}

using IPT::qr;
using IPT::qra;
using IPT::qrs;
using IPT::qrdb;
using OPT::qw;
using OPT::qwa;
using OPT::qws;

il ll calc(int l, int r){
ll h = (l + r + 1) / 2 ;
ll ret = sum[r] - sum[h] ;
ll d1 = 1ll * (h - l) * base[h] ;
ll d2 = 1ll * (r - h) * base[h] ;
    return ret - d2 + d1 - sum[h] + sum[l] ;
}
il ll trans(ll p, ll x){
    return f[p] + calc(p, x) ;
}
bool check(ll x){
stk[tp = 0] = 0 ;
    int h = 0 ; lrg[0] = 1 ;
    for (int i = 1 ; i <= n ; ++ i){
while (h < tp && lrg[h] < i)
++ h ; if (lrg[h] > i) -- h ;
        f[i] = trans(stk[h], i) + x, cnt[i] = cnt[stk[h]] + 1 ;
while (tp && trans(stk[tp], lrg[tp]) >= trans(i, lrg[tp]))
stk[tp] = 0, lrg[tp] = n + 1, -- tp ;
int l = lrg[tp], r = n, mid, ans = n + 1 ;
while (l <= r){
int mid = (l + r) >> 1 ;
if (trans(stk[tp], mid) >= trans(i, mid))
ans = mid, r = mid - 1 ; else l = mid + 1 ;
}
if (ans <= n) stk[++ tp] = i, lrg[tp] = ans ;
    }
    res = f[n] - x * m ; return (bool)(cnt[n] < m) ;
}
int main(){
    qr(n) ; qr(m) ;
for (int i = 1 ; i <= n ; ++ i)
qr(base[i]), sum[i] = sum[i - 1] + (ll)base[i] ;
ll l = 0, r = 1e9, mid, ans ;
    lrg[0] = 1 ; sum[n + 1] = sum[n] ;
while (l <= r){
mid = (l + r) >> 1 ;
if (check(mid)) r = mid - 1 ;
        else ans = mid, l = mid + 1 ;
}
    check(ans) ; qw(res) ; return 0 ;
}

IOI2000 邮局(环版本)

改成环上建 $k$ 个邮局了。数据范围还是不变的。

考虑破环为链的问题在于,$n\to 1$ 那边可能存在没有考虑到的问题,同时由于限制了邮局数量而不能在后面接成 $2n$ 的链。于是比较暴力的方法自然是随机化,随机第一个邮局的位置,那么显然需要随机 $>\frac{n}{k}$ 次,比如 $\frac{n}{k}\log n$ ,这样暴力做的复杂度就变成了 $O(nk\log n)\cdot O(\frac{n}{k}\log n)=O(n^2\log n)$ 。

考虑更好一点的做法。由于无论是在环上还是在链上,这个模型都满足四边形不等式,所以可以知道,任意两条不同起点的转移路径,一定要么重合,要么有 $k$ 个交点。所以可以随便选一个起点,跑一次dp,构造出转移路径来,假设是 $u_1\to u_2\to u_3\cdots\to u_k$ ,那么随便选择两个端点,比如 $u_p\to u_{p+1}$ ,可知最优解一定有一个转移点在 $u_p\to u_{p+1}$ 之间,那么只需要找到一组间隔最小的作为起点即可(环上的转移路径起点任意)。由于两点之间距离上界是 $O(\frac{n}{k})$ ,所以如果套用链里的 $O(n\log n\log V)$ 的做法,最终复杂度就是 $O(\frac{n^2}{k}\log n\log w)$ ,在 $k$ 很小的时候是不优的。

…思考了一下,似乎不知道当 $k$ 很小的时候有什么比较精妙的做法,因为无论怎么化,最后复杂度的大头都落在 $n$ 上emmm

好的吧,直接正解吧。考虑上面说的那个性质,假设最优解的转移路径为 $v_1\to v_2\to v_3\cdots v_k$ ,那么一定有

类似这样。那么可以知道类似于每一层找一个决策点,同时也由于决策单调性,只会同时出现在 $mid$ 的同一边,那么最终的决策数是 $\frac{n}{k}\cdot k\cdot \log n=n\log n$ ,再套一层分治,最终复杂度 $O(n\log ^2 n+n\log n\log V) 。$ 。

一个小细节,就是第一层需要 $<\frac{n}{k}$,这样才能保证决策数。

LG4983忘情

将一个长为 $n$ 的序列划分成 $m$ 段,每段 $[l,r]$ 的代价是

最小化这个代价。

$1\leq n\leq 10^5$ 。

首先提一下平方化一下式子得到代价本质上是

然后发现,这显然就是分的段越多越好,理想情况下(代价最小)就是分 $n$ 段。那么这个东西就显然是凸的,虽然是半凸壳但至少也是凸的。于是就去二分每分一段应该支付多少代价即可,似乎转移难度比上一道题还简单不少?

注意到二分内部写决策单调性是带 $\log$ 的,虽然我总觉得应该可以线性(但据dls说那种线性做法常数很大),于是复杂度就是 $n\log n\log V$ 的。不开 -O2 在谷的表现并不好,开了之后性能有了超大的飞跃。

代码没啥可贴的,我就是copy了上道题的代码然后改了改转移(

CF958E2

给定 $n$ 个时间点。每个区间都以某两个时间点为左右端点,且每个区间的「代价」定义端点的时间之差。你要选择 $k$ 个连续的区间,保证这个 $k$ 个连续的区间没有交集,且代价总和最小。

$1\leq n\leq 500000,1\leq k\leq 5000$

考虑一般 $dp$ 的话就是 $f_{i,j}$ ,这个地方由于不限制一定要取满,所以就可以有如下转移:

似乎常数小一点,暴力 $O(nk)$ 也是可以过的。于是就直接wqs二分一下,注意到由于此时最优的决策一定是少选,所以每选一次就需要减去 $mid$ 来维护这个限制。于是最后复杂度 $n\log V$ 。

需要注意的是,由于用了 $cnt_i$ 记录转移到 $i$ 这个状态至少要分成多少段,所以这个地方还是牵扯到一个,如果我可以有 $6/7/8$ 三种划分方式转移到最优解,那么到底应该用哪个。很显然的是要么用 $max$ 要么用 $min$,这取决于二分的方式。如果是取 $max$ 的话,那么可能 $cnt_n>m$ ;取 $min$ 的话则会 $\leq m$ 。所以根据这个调整代码细节就好了。

┮﹏┭这个地方真的是坑了我好久。画外音: 你Tree I那题白做了??

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
ll res ;
ll f[N] ;
int m, n ;
int df[N] ;
int cnt[N] ;
int base[N] ;

bool check(int x){
x *= -1 ;
for (int i = 2 ; i <= n ; ++ i){
if (f[i - 1] < f[i - 2] + df[i] + x)
f[i] = f[i - 1], cnt[i] = cnt[i - 1] ;
else f[i] = f[i - 2] + (ll)df[i] + (ll)x, cnt[i] = cnt[i - 2] + 1 ;
if (f[i - 1] == f[i - 2] + df[i] + x) cnt[i] = max(cnt[i - 1], cnt[i - 2] + 1) ;
}
res = f[n] - (ll)x * m ; return (bool)(cnt[n] >= m) ;
}
int main(){
cin >> m >> n ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]) ;
sort(base + 1, base + n + 1) ;
for (int i = 1 ; i <= n ; ++ i)
df[i] = base[i] - base[i - 1] ;
int l = 0, r = 1e9, mid, ans ;
while (l <= r){
mid = (l + r) >> 1 ;
// cout << l << " " << r << endl ;
if (check(mid)) ans = mid, r = mid - 1 ;
else l = mid + 1 ;
}
check(ans) ; cout << res << endl ; return 0 ;
}

[国家集训队]种树

就是那个围着坑种树. 要求必须种 K 棵。

首先由于 $m$ 的限制,加上权值会有负数所以多选和少选都有可能导致结果不优,所以很容易想到要去wqs二分。二分之后就变成了求解没有 $m$ 的限制的最大值问题。自然的想法是考虑 $f_i$ 表示前 $i$ 个坑种树的最大收益,那么转移就是考虑第 $i$ 个坑种不种,即 $f_i=\max\{f_{i-1},f_{i-2}+val_i\} $ 。

但是这个地方存在一个问题,就是第 $n$ 个和第 $1$ 个之间可能存在不合法。于是就理所应当地再记一维 $0/1$ 表示第 $1$ 个坑到底种不种树,转移到 $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
ll res ;
int m, n ;
int df[N] ;
ll f[N][2] ;
int base[N] ;
int cnt[N][2] ;

bool check(int x){
f[1][0] = 0 ; cnt[1][0] = 0 ;
f[1][1] = base[1] + x, cnt[1][1] = 1 ;
for (int i = 2 ; i < n ; ++ i){
if (f[i - 1][0] > f[i - 2][0] + x + base[i])
f[i][0] = f[i - 1][0], cnt[i][0] = cnt[i - 1][0] ;
else if (f[i - 1][0] < f[i - 2][0] + x + base[i])
f[i][0] = f[i - 2][0] + x + base[i], cnt[i][0] = cnt[i - 2][0] + 1 ;
else
f[i][0] = f[i - 1][0], cnt[i][0] = max(cnt[i - 1][0], cnt[i - 2][0] + 1) ;

if (f[i - 1][1] > f[i - 2][1] + x + base[i])
f[i][1] = f[i - 1][1], cnt[i][1] = cnt[i - 1][1] ;
else if (f[i - 1][1] < f[i - 2][1] + x + base[i])
f[i][1] = f[i - 2][1] + x + base[i], cnt[i][1] = cnt[i - 2][1] + 1 ;
else
f[i][1] = f[i - 1][1], cnt[i][1] = max(cnt[i - 1][1], cnt[i - 2][1] + 1) ;
}
f[n][1] = f[n - 1][1] ;
cnt[n][1] = cnt[n - 1][1] ;
if (f[n - 1][0] > f[n - 2][0] + x + base[n])
f[n][0] = f[n - 1][0], cnt[n][0] = cnt[n - 1][0] ;
else if (f[n - 1][0] < f[n - 2][0] + x + base[n])
f[n][0] = f[n - 2][0] + x + base[n], cnt[n][0] = cnt[n - 2][0] + 1 ;
else
f[n][0] = f[n - 1][0], cnt[n][0] = max(cnt[n - 1][0], cnt[n - 2][0] + 1) ;
if (f[n][0] > f[n][1]){
res = f[n][0] - (ll)x * m ;
return (bool)(cnt[n][0] >= m) ;
}
else{
res = f[n][1] - (ll)x * m ;
return (bool)(cnt[n][1] >= m) ;
}
}
int main(){
cin >> n >> m ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]) ;
if (m > n / 2) return puts("Error!"), 0 ;
int l = -2e9, r = 2e9, mid, ans ;
while (l <= r){
mid = (l + r) >> 1 ;
// cout << l << " " << r << endl ;
if (check(mid)) ans = mid, r = mid - 1 ;
else l = mid + 1 ;
}
check(ans) ; cout << res << endl ; return 0 ;
}

嗯,然后就没有然后了,感觉wqs二分还是偏套路的。

btw,我才发现原来LG上种树这题的两个版本不是同一道题,那个蓝色要求至多k个,所以不可以wqs随便搞.jpg