跳转至

整体二分

引子

在信息学竞赛中,有一部分题可以使用二分的办法来解决。但是当这种题目有多次询问且每次询问我们对每个查询都直接二分,可能会收获一个 TLE 。这时候我们就会用到整体二分。整体二分的主体思路就是把多个查询一起解决。(所以这是一个离线算法)

可以使用整体二分解决的题目需要满足以下性质:

  1. 询问的答案具有可二分性

  2. 修改对判定答案的贡献互相独立,修改之间互不影响效果

  3. 修改如果对判定答案有贡献,则贡献为一确定的与判定标准无关的值

  4. 贡献满足交换律,结合律,具有可加性

  5. 题目允许使用离线算法

——许昊然《浅谈数据结构题几个非经典解法》

思路

[l,r]为答案的值域,[L,R]为答案的定义域。(也就是说求答案时仅考虑下标在区间 [L,R]内的操作和询问,这其中询问的答案在 [l,r]内 )

  • 我们首先把所有操作按时间顺序存入数组中,然后开始分治。
  • 在每一层分治中,利用数据结构(常见的是树状数组)统计当前查询的答案和 mid之间的关系。
  • 根据查询出来的答案和 mid间的关系(小于等于 mid和大于 mid)将当前处理的操作序列分为 q1q2两份,并分别递归处理。
  • l=r时,找到答案,记录答案并返回即可。

需要注意的是,在整体二分过程中,若当前处理的值域为 [l,r],则此时最终答案范围不在 [l,r]的询问会在其他时候处理。

详解

注: 1. 为可读性,文中代码或未采用实际竞赛中的常见写法。 2. 若觉得某段代码有难以理解之处,请先参考之前题目的解释, 因为节省篇幅解释过的内容不再赘述。

从普通二分说起:

查询第k小:一次二分多个询问

题1 在一个数列中查询第 k小的数。

当然可以直接排序。如果用二分法呢?可以用数据结构记录每个大小范围内有多少个数,然后用二分法猜测,利用数据结构检验。

题2 在一个数列中多次查询第 k小的数。

可以对于每个询问进行一次二分;但是,也可以把所有的询问放在一起二分。

先考虑二分的本质:假设要猜一个 [l,r]之间的数,猜测之后会知道是猜大了,猜小了还是刚好。当然可以从 l枚举到 r,但更优秀的方法是二分:猜测答案是m = \lfloor\frac{l + r}{2}\rfloor,然后去验证 m的正确性,再调整边界。这样做每次询问的复杂度为 O(n\log_2 n),若询问次数为 q,则时间复杂度为 O(qn\log_2 n)

回过头来,对于当前的所有询问,可以去猜测所有询问的答案都是 mid,然后去依次验证每个询问的答案应该是小于等于 mid的还是大于 mid的,并将询问分为两个部分(不大于/大于),对于每个部分继续二分。注意:如果一个询问的答案是大于 mid的,则在将其划至右侧前需更新它的 k,即,如果当前数列中小于等于 mid的数有 t个,则将询问划分后实际是在右区间询问第 k - t小数。如果一个部分的 l = r了,则结束这个部分的二分。利用线段树的相关知识,我们每次将整个答案可能在的区间 [1,maxans]划分成了若干个部分,这样的划分共进行了 O(\log_2 maxans)次,一次划分会将整个操作序列操作一次。若对整个序列进行操作,并支持对应的查询的时间复杂度为 O(T),则整体二分的时间复杂度为 O(T\log_2 n)

试试完成以下代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
struct Query
{
    int id, k; // 这个询问的编号, 这个询问的k
};
int ans[N]; // ans[i] 表示编号为i的询问的答案
int check( int x ); // 返回原数列中小于等于x的数的个数
void solve( int l, int r, vector<Query> q )
// 请补全这个函数
{
    int m = ( l + r ) / 2;
    vector<Query> q1, q2; // 将被划到左侧的询问和右侧的询问
    if ( l == r )
    {
        // ...
        return;
    }
    // ...
    solve( l, m, q1 ), solve( m + 1, r, q2 );
    return;
}

参考代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void solve( int l, int r, vector<Query> q )
{
    int m = ( l + r ) / 2;
    if ( l == r )
    {
        for ( unsigned i = 0; i < q.size( ); i++ )
            ans[q[i].id] = l;
        return;
    }
    vector<int> q1, q2;
    for ( unsigned i = 0; i < q.size( ); i++ )
        if ( check( m ) <= q[i].k )
            q1.push_back( q[i] );
        else
            q[i].k -= check( m ), q2.push_back( q[i] );
    solve( l, m, q1 ), solve( m + 1, r, q2 );
    return;
}

区间查询第k小:对只询问指定区间的处理

题3 在一个数列中多次查询区间第 k小的数。

涉及到给定区间的查询,再按之前的方法进行二分就会导致 check 函数的时间复杂度爆炸。仍然考虑询问与值域中点 m的关系:若询问区间内小于等于 m的数有 t个,询问的是区间内的 k小数,则当 k \leq t时,答案应小于等于 m;否则,答案应大于 m。(注意边界问题)此处需记录一个区间小于等于指定数的数的数量,即单点加,求区间和,可用树状数组快速处理。为提高效率,只对数列中值在值域区间 [l,r]的数进行统计,即,在进一步递归之前,不仅将询问划分,将当前处理的数按值域范围划为两半。

参考代码(关键部分)

 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
struct Num
{
    int p, x;
}; // 位于数列中第 p 项的数的值为 x
struct Query
{
    int l, r, k, id;
}; // 一个编号为 id, 询问 [l,r] 中第 k 大数的询问
int ans[N];
void add( int p, int x ); // 树状数组, 在 p 位置加上 x
int query( int p ); // 树状数组, 求 [1,p] 的和
void clear( ); // 树状数组, 清空
void solve( int l, int r, vector<Num> a, vector<Query> q )
// a中为给定数列中值在值域区间 [l,r] 中的数
{
    int m = ( l + r ) / 2;
    if ( l == r )
    {
        for ( unsigned i = 0; i < q.size( ); i++ )
            ans[q[i].id] = l;
        return;
    }
    vector<Num> a1, a2;
    vector<Query> q1, q2;
    for ( unsigned i = 0; i < a.size( ); i++ )
        if ( a[i].x <= m )
            a1.push_back( a[i] ), add( a[i].p, 1 );
        else
            a2.push_back( a[i] );
    for ( unsigned i = 0; i < q.size( ); i++ )
    {
        int t = query( q[i].r ) - query( q[i].l - 1 );
        if ( q[i].k <= t )
            q1.push_back( q[i] );
        else
            q[i].k -= t, q2.push_back( q[i] );
    }
    clear( );
    solve( l, m, a1, q1 ), solve( m + 1, r, a2, q2 );
    return;
}

带修区间第k小:整体二分的完整运用

题4 Dynamic Rankings 给定一个数列,要支持单点修改,区间查第 k小。

修改操作可以直接理解为从原数列中删去一个数再添加一个数,为方便起见,将询问和修改统称为“操作”。因后面的操作会依附于之前的操作,不能如题3一样将统计和处理询问分开,故可将所有操作存于一个数组,用标识区分类型,依次处理每个操作。为便于处理树状数组,修改操作可分拆为擦除操作和插入操作。

优化

  1. 注意到每次对于操作进行分类时,只会更改操作顺序,故可直接在原数组上操作。具体实现,在二分时将记录操作的 q, a数组换为一个大的全局数组,二分时记录信息变为 L, R,即当前处理的操作是全局数组上的哪个区间。利用临时数组记录当前的分类情况,进一步递归前将临时数组信息写回原数组。
  2. 树状数组每次清空会导致时间复杂度爆炸,可采用每次使用树状数组时记录当前修改位置(这已由1中提到的临时数组实现),本次操作结束后在原位置加 -1的方法快速清零。
  3. 一开始对于数列的初始化操作可简化为插入操作。

关键部分参考代码

 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
struct Opt
{
    int x, y, k, type, id;
    // 对于询问, type = 1, x, y 表示区间左右边界, k 表示询问第 k 小
    // 对于修改, type = 0, x 表示修改位置, y 表示修改后的值,
    // k 表示当前操作是插入(1)还是擦除(-1), 更新树状数组时使用.
    // id 记录每个操作原先的编号, 因二分过程中操作顺序会被打散
};
Opt q[N], q1[N], q2[N];
// q 为所有操作,
// 二分过程中, 分到左边的操作存到 q1 中, 分到右边的操作存到 q2 中.
int ans[N];
void add( int p, int x );
int query( int p ); // 树状数组函数, 含义见题3
void solve( int l, int r, int L, int R )
// 当前的值域范围为 [l,r], 处理的操作的区间为 [L,R]
{
    if ( l > r || L > R )
        return;
    int cnt1 = 0, cnt2 = 0, m = ( l + r ) / 2;
    // cnt1, cnt2 分别为分到左边, 分到右边的操作数
    if ( l == r )
    {
        for ( int i = L; i <= R; i++ )
            if ( q[i].type == 1 )
                ans[q[i].id] = l;
        return;
    }
    for ( int i = L; i <= R; i++ )
        if ( q[i].type == 1 )
        { // 是询问: 进行分类
            int t = query( q[i].y ) - query( q[i].x - 1 );
            if ( q[i].k <= t )
                q1[++cnt1] = q[i];
            else
                q[i].k -= t, q2[++cnt2] = q[i];
        }
        else
            // 是修改: 更新树状数组 & 分类
            if ( q[i].y <= m )
                add( q[i].x, q[i].k ), q1[++cnt1] = q[i];
            else
                q2[++cnt2] = q[i];
    for ( int i = 1; i <= cnt1; i++ )
        if ( q1[i].type == 0 )
            add( q1[i].pos, -q1[i].k ); // 清空树状数组
    for ( int i = 1; i <= cnt1; i++ )
        q[L + i - 1] = q1[i];
    for ( int i = 1; i <= cnt2; i++ )
        q[L + cnt1 + i - 1] = q2[i]; // 将临时数组中的元素合并回原数组
    solve( l, m, L, L + cnt1 - 1 ), solve( m + 1, r, L + cnt1, R );
    return;
}

参考习题

「国家集训队」 矩阵乘法

「POI2011 R3 Day2」流星 Meteors

参考资料

  • 许昊然《浅谈数据结构题几个非经典解法》

评论