简介

整体二分，又被称为“基于值域的整体分治算法”，这类离线分治算法基于值域(答案范围)对整个操作序列(包括修改、查询)进行分治，使操作序列在保持时间顺序的基础上能够同值域一起划分为独立的子问题，故被称为基于值域的整体分治算法，简称“整体二分、整体分治”。

什么样的问题适合“整体二分”

• 1.询问的答案具有可二分性（单调）

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

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

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

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

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

基本过程

如果问题符合整体二分要求，整体二分基本过程如下：

• 1.将所有修改和询问 按时间顺序 存入数组，按照值域进行分治。（实际分治过程中不会改变时间轴前后顺序）
• 2.递归边界：操作系列为空时，直接返回。当值域 $lval==rval$ , 保存答案，返回。
• 3.否则依次扫描原操作序列，按值域将原操作分为左和右，递归左右子问题。 原问题值域范围设置为 $[lval,rval]$ ,值域中点 $mid=\frac{lval+rval}{2}$。
  • 依次扫描所有操作，将操作分成落在值域 $[lval,mid]$ 还是落在 $[mid+1,rval]$ 内。
  • 对于修改，只需要考虑修改的值落在 $[lval,mid]$ 的影响（或者落在后半部分），利用数据结构维护修改。
  • 对于询问，利用数据结构查询，考虑询问落在 $[lval,mid]$ 还是落在 $[mid+1,rval]$ 内。

以区间第 $k$ 小为例，按值域分治，示意图如下：

例1. 静态区间第 k 小 P3834可持久化线段树

【题意简化】给定 $n(\le 2 \times 10^5)$ 个整数构成的序列 $a$，$m(\le 2 \times 10^5)$ 次询问, 查询闭区间 $[l,r]$ 内的第 $k$ 小值。

【分析】本题是经典问题“静态区间第 $k$ 小”，可以采用“可持久化线段树”、“整体二分”、“树套树”等方法解决。

【参考代码】整体二分

例2. 动态区间第 k 小P2617 Dynamic Rankings

【题意简化】给定一个含有 $n(\le 10^5)$ 个数的序列 $a_1,a_2,\dots,a_n$ ，$m(\le 10^5)$ 次操作 ，操作分为两种：

• Q l r k 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数；
• C x y 表示将 $a_x$ 改为 $y$

【分析】带修改的区间第 $k$ 小

【参考代码】整体二分

例3. 静态矩阵第 k 小 P1527 [国家集训队] 矩阵乘法

【题意简化】给你一个 $n \times n(n\le 500)$ 的矩阵，$q(\le 6\times 10^4)$ 次询问，每次询问一个子矩形的第 $k$ 小数。

【分析】利用二维树状数组，计算小矩阵内点的个数。整体二分整体处理多次询问。

【参考代码】整体二分

例4. P3332 K 大数查询

【题意简化】维护 $n$ 个可重整数集，集合的编号从 $1$ 到 $n$。 这些集合初始都是空集，有 $m$ 个操作：

• 1 l r c：表示将 $c$ 加入到编号在 $[l,r]$ 内的集合中
• 2 l r c：表示查询编号在 $[l,r]$ 内的集合的并集中，第 $c$ 大的数是多少。

【分析】按照值域进行二分，对于 $c\le mid$ 的修改，在位置上修改，即在区间 $[l,r]$ 加 $1$. 对于查询，按位置做区间查询。使用线段树做区间修改，区间查询。

【参考答案】整体二分

例5. 区间前驱后继

例6. P3527 [POI 2011] MET-Meteors

【题意简化】给出一个环形序列，被分为 $m$ 段。有 $n$ 个国家，序列的第 $i$ 段属于国家 $o_i$ 。接下来有 $k$ 次事件，每次给环形序列上的一个区间加上一个正整数。每个国家有一个期望 $p_i$ ，求出每个国家在序列上所有位置的值的和到达 $p_i$ 的最早时间（或报告无法达到）。

【分析】

【参考代码】点击

---

构造单调性序列

例7. P4597 序列 sequence

【题意简化】给定一个长度为 $n$ 的序列，每次操作可以把某个数 $+1$ 或 $-1$，要求将序列变成单调不下降的，询问最少操作次数是多少？

【分析】本题可以用动态规划或反悔贪心求解。这里介绍整体二分构造一组答案，然后再求最少次数。

对于原序列区间 $[l,r]$ 的数,值域范围是 $[lval,rval]$. 将序列前一部分 $[l,i]$ 变为 $mid$, $[i+1,r]$ 变为 $mid+1$ ,如果操作次数减少，那么就可以分治递归解决两个子问题，子问题1：将序列 $[l,i]$ 变为值域为 $[lval,mid]$; 子问题2：将序列 $[i+1,r]$ 变为 $[mid+1,rval]$ . 不断递归直到区间不存在或者值域区间变为单点。

核心代码：

int n,a[N],ans[N];
void sol(int l,int r,int lval,int rval)
{
    if(l>r)return;
    if(lval==rval)
    {
        for(int i=l;i<=r;i++)ans[i]=lval;
        return;
    }
    int mid=(lval+rval)>>1;
    ll sum=0;
    for(int i=l;i<=r;i++)sum+=abs(a[i]-(mid+1));
    ll ret=sum;
    int p=l-1;   //初始 0 个数分到 [lval,mid]
    for(int i=l;i<=r;i++)  //[l,i] 的数变为 mid 值更小
    {
        sum-=abs(a[i]-(mid+1));
        sum+=abs(a[i]-mid);
        if(ret>sum)ret=sum,p=i;        
    }
    sol(l,p,lval,mid);
    sol(p+1,r,mid+1,rval);
}

【参考代码】点击

类似题目 P4331 [BalticOI 2004] Sequence (Day1)

【分析】整体二分构造的是单调递增序列，不能保证严格递增，为了保证严格递增，可以在 ans[i]+=i , 那么原序列 a[i]-=i, 之后再改回去.

【参考代码】点击

学习完毕

{{ select(1) }}

• YES
• NO