CDQ分治与整体二分

0. 前言

你需要知道——分治。
对于我们介绍的CDQ分治和整体二分，他们都属于离线分治算法的一类。

1. CDQ 分治

1.1 分治的经典应用

分治一个经典应用就是归并排序，我们可以参考它的运行过程。

回忆一下归并排序的步骤？

1. 把数组分成$[l,mid],[mid+1,r]$ 两个区间。
2. 对左区间和右区间进行归并排序。
3. 把左区间和有区间合并为一个有序数组。

这里引用GTWZeus大佬的文章的图：

ok回忆完了分治的结构，记住这个图的结构，我们来看 CDQ 分治。

1.2 基于时间的分治算法

CDQ 分治不是一个模板，它是一个思想。

大多数数据结构问题都可以抽象为：“维护一堆数据，对一系列操作依次作出响应” 的形式。而这些操作一般分为所谓的 “查询” 操作或者 “更新” 操作。
而查询操作和更新操作也是有问题类型划分的。如果所有查询操作都在更新操作之后，那么这个问题就是一个静态问题。反之则为动态问题。 ——蓝书（非原文）

一般来说我们在做数据结构遇到的到多数都是动态问题，我们要想出来一个维护方法很难，而对于静态问题却很好做。CDQ分治就能做到将动态问题拍扁成静态问题。

我们将所有操作横向展开画在以 “时间” 为横坐标平面轴上，我们观察修改操作，发现它只会对在它后面出现的操作产生影响。

那么我们可不可以这样想，对于操作序列中每一个查询，计算查询结果就是 “计算初始数据+在该查询之前所有修改“ 所造成的影响。

我们可以将每个操作对后续操作的贡献图画出来，在这里实线箭头表示对后续操作有贡献（修改），虚线即为无贡献（查询）。

我们对于操作不断向上合并贡献，如果一个操作区间有了对后继操作有贡献，我们也把这个区间的线全表为实线。

这个结构…怎么这么像归并排序的结构？

我们不妨试试分治，对于一个操作序列有$m$ 项操作。$\forall l,r \in [1,m]$，我们定义$solve(l,r)$ 为：

$\forall k \in [l,r]$，若第$k$ 项操作是查询操作，那么我们就计算$[l,k-1]$ 里面操作对当前操作的影响，实际上就是分治的思想，我们区间砍成一半$[l,mid],[mid+1,r]$，对左右区间递归计算，让后计算$[l,mid]$ 中修改操作对$[mid+1,r]$ 的查询操作影响。

我们还需要证明这样分治是正确的：

• 若第$k$ 个操作是查询操作，若$k\le mid$ 那么$solve(l,mid)$ 已经计算了$[l,k-1]$ 操作对它的影响，反之$k>mid$，同理珂证明$solve(mid+1,r)$ 计算了操作对它的影响，再加上$solve(l,mid)$ 的影响。得证。
• 修改操作？我们计算查询贡献的。

总结一下 CDQ 分治有三个操作：

1. 递归左区间$solve(l,mid)$。
2. 递归右区间$solve(mid+1,r)$。
3. 计算左区间修改操作对右区间的影响。
   当$l=r$ 时是递归边界，因为这还怎么递归，操作3都走不了www。

对于递归树如下，借用oiwiki的图：

那不对啊，你一开始说这个分治能把我不会的动态问题派扁成静态，哪里拍扁了？

你看第三个操作，左右区间里面单独的查询修改操作已经操作完毕，我们只需要算左区间单独的修改操作对右区间查询操作的影响即可，这个难道不就是静态问题吗，肯定是的。

这样的话，CDQ 分治就把一个动态问题划分成$m$ 个静态问题，每个查询结果是由$\log m$ 个静态问题的结果共同造成的。

静态问题当然比动态问题好做多啦，如果我们对于操作 3 能做到仅在$r-l$ 的规模内完成，和$m$ 无关，那么我们就能以优秀的时间复杂度，多个$O(\log m)$ 的代价做削弱版本的问题，这是十分甚至九分好的，这样的总时间复杂度就是$O((n+m)\log^2 (n+m))$。

接下来我们来看例题：

洛谷P4169 [Violet] 天使玩偶/SJY摆棋子

假如说没有$t=1$ 的操作我们看看怎么做，根据题意，答案就是：

$$\min_{i=1}^n \left\{ |x-x_i|+|y-y_i| \right\}$$

我们看看这个怎么去掉绝对值符号，先拆掉试试。

$$\min_{i=1}^n \left\{ (x-x_i)+(y-y_i) \right\}$$

不难发现$x,y$ 是定值，考虑提出来。

$$(x+y)-\max_{i=1}^n (x_{i}+y_{i})$$

但是这样拆有个前提条件，我们的$(x_i,y_i)$ 坐标必须在左下角，但是点在四面八方怎么办？我们充分发挥人类智慧，直接旋转坐标系让他们移动到左下角，或者不用旋转直接平移就可以了。

暴力当然是$O(n^2)$ 的，我们考虑怎么做到$O(n \log n)$ ，直接上数据结构，先按照$x_i$ 从小到大排序 ，树状数组以$y_i$ 为下标，对于$x+y$ 取最大值就可以了。

有修改怎么做？发现可以离线，直接上CDQ！

但是注意一下，我们不能每个$solve$ 都搞一个树状数组，那样时间和空间都会爆炸，我们要保证时间复杂度仅与$r-l$ 相关，要在计算贡献完后清空树状数组影响的部分。时间复杂度$O(q\log^2 q)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15,INF=0x3f3f3f3f;
struct Query
{
    int x,y,op,id;
}a[MN],b[MN],tmp[MN];
int n,m,mxlen,ans[MN];

struct mxBIT{
    int t[MN];

    int lowbit(int x){
        return x&-x;
    }

    int query(int x){
        int ret=-INF;
        while(x){
            ret=max(ret,t[x]);
            x-=lowbit(x);
        }
        return ret;
    }

    void update(int x,int k){
        while(x<MN){
            t[x]=max(t[x],k);
            x+=lowbit(x);
        }
    }

    void clear(int x){
        while(x<MN&&t[x]){
            t[x]=-INF;
            x+=lowbit(x);
        }
    }

}bit;

void cdq(int l,int r){
    // cout<<l<<" "<<r<<'\n';
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(j<=r){
        while(b[i].x<=b[j].x&&i<=mid){
            if(b[i].op==1) bit.update(b[i].y,b[i].x+b[i].y);
            tmp[k++]=b[i++];
        }
        if(b[j].op==2){
            ans[b[j].id]=min(ans[b[j].id],b[j].x+b[j].y-bit.query(b[j].y));
        }
        tmp[k++]=b[j++];
    }
    for(int p=l;p<i;p++){
        if(b[p].op==1) bit.clear(b[p].y);
    }
    while(i<=mid) tmp[k++]=b[i++];
    for(int p=l;p<=r;p++) b[p]=tmp[p];
}

void solve(int x,int y){
    for(int i=1;i<=n+m;i++){
        b[i]=a[i];
        if(x) b[i].x=mxlen-b[i].x;
        if(y) b[i].y=mxlen-b[i].y;
    }
    cdq(1,n+m);
}

int main(){
    memset(bit.t,-0x3f,sizeof(bit.t));
    memset(ans,0x3f,sizeof(ans));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        a[i].id=i;
        a[i].op=1;// 1是插入，除此以外都为查询
        a[i].x++;
        a[i].y++;
        mxlen=max({mxlen,a[i].x,a[i].y});
    }
    for(int i=n+1;i<=n+m;i++){
        int op,x,y;
        cin>>op>>x>>y;
        a[i].op=op;
        a[i].x=++x;
        a[i].y=++y;
        mxlen=max({mxlen,a[i].x,a[i].y});
        a[i].id=i;
    }
    mxlen++;
    solve(0,0);
    solve(1,0);
    solve(0,1);
    solve(1,1);
    for(int i=n+1;i<=n+m;i++){
        if(a[i].op==2) cout<<ans[i]<<'\n';
    }
    return 0;
}

1.3 基于钉死一维的点对问题分治算法

这个名字有点形象www。
CDQ 分治不仅能时间分治，还能解决点对问题。

来看三维偏序例题：

有$n$ 个元素，第$i$ 个元素有$a_i,b_i,c_i$ 三个属性，设$f(i)$ 表示满足$a_j \leq a_i$ 且$b_j \leq b_i$ 且$c_j \leq c_i$ 且$j \ne i$ 的$j$ 的数量。
对于$d \in [0, n)$，求$f(i) = d$ 的数量。

我们回忆一下二维偏序（逆序对）问题我们是怎么做的，我们不会二维所以我们考虑先钉死一维，比如说$i<j$ 就很好钉死，另一维$a_i>a_j$ 很好做，用权值树状数组做就可以了。

但是二维偏序还有一个解法就是归并排序，事实上归并排序也是定死一维$i<j$ ，让后分治的处理$a_i>a_j$。

那么对于三维偏序呢？我们是不是也可以想上面钉死一维度呢？但是好像轻易的钉死会出事，因为对于当前第一维度的位置，前面的偏序对后面偏序也会造成影响，这告诉我们什么？CDQ分治！

我们像上面例题的解决方法一样，先对于$a_i$ 进行排序，CDQ分治先递归$solve(l,mid),solve(mid+1,r)$，接下来要开始计算前对后的影响。

仔细思考可以发现$a_i$ 的排序已经没啥用了，因为在 CDQ 分治中左区间和右区间的计算已经满足的$a_i$ 的限制了，于是接下来我们可以看剩下两个限制，接下来就是一个最经典的二维偏序问题了，做就可以了。

这样的时间复杂度还是一样的$O(n\log^2 n)$。

仔细思考一下，CDQ 分治一个天然的特性它能满足一个维度的限制，对于时间分治他能天然的满足$time_i<time_j$。对于本题来说，通过先对$a_i$ 排序，CDQ分治能做到天然的满足三维偏序中的$a_i$ 偏序，这样就大大将问题简化为二维偏序问题。

事实上，CDQ分治的一个核心特性是通过分治策略逐层处理多维问题中的单个维度限制 ，从而将高维问题转化为低维问题。通过在每一步递归中主动构造一个维度的有序性（注意我们是在内部进行排序而非外部，不然就摁死不了一维了），天然的满足一个维度的限制条件。

代码如下：

#include <bits/stdc++.h>
using namespace std;
constexpr int MN=2e5+15;
struct Node{
    int x,y,z,ans,cnt;
}a[MN],b[MN];
int n,K,tot,cnt[MN],t[MN];

struct BIT{
    int t[MN];

    inline int lowbit(int x){
        return x&-x;
    }

    void update(int x,int k){
        while(x<MN){
            t[x]+=k;
            x+=lowbit(x);
        }
    }

    int query(int x){
        int ret=0;
        while(x){
            ret+=t[x];
            x-=lowbit(x);
        }
        return ret;
    }

}bit;

bool cmp1(Node x,Node y){
    if(x.x==y.x){
        if(x.y==y.y) return x.z<y.z;
        return x.y<y.y;
    }
    return x.x<y.x;
}

bool cmp2(Node x,Node y){
    if(x.y==y.y) return x.z<y.z;
    return x.y<y.y;
}

void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l, mid);
    cdq(mid+1,r);
    sort(a+l,a+mid+1,cmp2);
    sort(a+mid+1,a+r+1,cmp2);
    int i=mid+1,j=l;
    while(i<=r){
        while(a[j].y<=a[i].y&&j<=mid){
            bit.update(a[j].z,a[j].cnt);
            j++;
        }
        a[i].ans+=bit.query(a[i].z);
        i++;
    }
    for(int i=l;i<j;i++){
        bit.update(a[i].z,-a[i].cnt);
    }
}

int main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        cin>>b[i].x>>b[i].y>>b[i].z;
    }
    sort(b+1,b+1+n,cmp1);//先钉死一维
    int c=0;
    for(int i=1;i<=n;i++){
        c++;
        if(b[i].x!=b[i+1].x||b[i].y!=b[i+1].y||b[i].z!=b[i+1].z){
            a[++tot]=b[i];
            a[tot].cnt=c;
            c=0;
        }
    }
    cdq(1,tot);
    for(int i=1;i<=tot;i++){
        cnt[a[i].ans+a[i].cnt-1]+=a[i].cnt;
    }
    for(int i=0;i<n;i++) cout<<cnt[i]<<'\n';
    return 0;
}

更一般的，我们总结为以下问题：

给定一个长度为$n$ 的序列，统计有一些特性的点对$(i,j)$ 的数量/找到一对点对$(i,j)$ 使得一些函数的值最大。

流程如下：

• 找到序列中点$mid$。
• 对于所有点对分3类：
  • $(i,j)$ 在左区间的。
  • $(i,j)$ 跨区间的,指$i$ 在左区，$j$ 在右区。
  • $(i,j)$ 在右区间的。
• 递归处理左右区间，设计算法处理跨区间点对。

我们其实发现，对于基于时间的分治算法和这个也极为相似，同样都是要解决跨区间的问题，递归处理左右区间的算法。

洛谷P3157 [CQOI2011] 动态逆序对

一个不难发现就是其实删除操作也是更新操作（废话）, 考虑有贡献的点对$(i,j)$，转成三维偏序话就是两个逆序对。

对于每一个被删的元素，消失的逆序对等于
在它前面，权值比他大，且删去时间比他晚的点个数
在它后面，权值比他小，且删去时间比他晚的点个数
——shadowice1984大佬

$$\begin{aligned} time_{i}<time_{j},i<j,a_{i}>a_{j} \\ time_{i}<time_{j},i>j,a_{i}<a_{j} \end{aligned}$$

这样的话直接做！

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=3e5+15;
struct Query{
    int op,x,y,t,id;
}q[MN];
int n,m,qtot,ans[MN],a[MN],pos[MN];

struct BIT{
    int t[MN];

    int lowbit(int x){
        return x&-x;
    }

    void update(int x,int k){
        while(x<MN){
            t[x]+=k;
            x+=lowbit(x);
        }
    }

    int query(int x){
        int ret=0;
        while(x){
            ret+=t[x];
            x-=lowbit(x);
        }
        return ret;
    }

}bit;

bool cmp2(Query x,Query y){
    return x.x<y.x;
}

void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int i=l,j=mid+1;
    sort(q+l,q+mid+1,cmp2);
    sort(q+mid+1,q+r+1,cmp2);
    while(j<=r){
        while(q[i].x<=q[j].x&&i<=mid){
            bit.update(q[i].y,q[i].op);
            i++;
        }
        ans[q[j].id]+=q[j].op*(bit.query(n)-bit.query(q[j].y));
        j++;
    }
    for(int p=l;p<i;p++){
        bit.update(q[p].y,-q[p].op);
    }
    i=r,j=mid;
    while(i>mid){
        while(j>=l&&q[j].x>=q[i].x) bit.update(q[j].y,q[j].op),j--;
        ans[q[i].id]+=q[i].op*bit.query(q[i].y-1);
        i--;
    }
    for(i=mid;i>j;i--) bit.update(q[i].y,-q[i].op);
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]]=i;
        q[++qtot]={1,i,a[i],0,0};
    }
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        q[++qtot]={-1,pos[x],x,i,i};// 1是加入，-1是删除
    }
    // sort(q+1,q+1+qtot,cmp1); 已经满足时间从前往后了所以不用排序。
    cdq(1,qtot);
    for(int i=1;i<=m;i++) ans[i]+=ans[i-1];
    for(int i=0;i<m;i++) cout<<ans[i]<<'\n';
    return 0;
}

P4690 [Ynoi Easy Round 2016] 镜中的昆虫

维护一个长为 $n$ 的序列 $a_i$，有 $m$ 次操作。

1. 将区间 $[l,r]$ 的值修改为 $x$。

2. 询问区间 $[l,r]$ 出现了多少种不同的数，也就是说同一个数出现多次只算一个。
   $1\leq n , m \leq 10^5$，$1\leq a_i\leq 10^9$。

经典的颜色段问题，但是加强版。
珂朵莉树？你看看这是谁出的题。
带修莫队，疯了吧 。

怎么做？发现可以离线哦，而且$a_i$ 可以离散化。
先考虑不修改怎么做，在不能用莫队和珂朵莉树的情况下，我们可以开一个$pre$ 数组，对于$pre_i$ 表示当前节点颜色在它左侧第一个和它同色点的位置，这个位置可以$O(n)$ 求出来。

对于区间询问其实就是询问$[l,r]$ 中$pre_{i}< l$ 的数有多少个，用线段树或树状数组即可做，我们看作二维数点$(i,pre_i)$，实际上就是一个二维偏序问题吗，树状数组做即可。

那么有单点修改呢？单点修改有点炸裂我不会做在线（分块写的很少的蒟蒻），我们可以利用上面的CDQ时间分治做，考虑一次修改对于$pre$ 数组会造成什么影响？显然只会对后继第一个同色点有影响，我们可以对每个颜色开一个 set，直接$O(\log n)$ 查询后继，$O(1)$ 修改即可。

那区间修改呢？你确定区间修改不会炸到$O(nm)$ ？

其实是$O(n+m)$ （我一直以为会炸$O(nm)$ ）？

为什么？我们不妨考虑一个极端情况，一个相同数的最长连续段作为一个节点（其实就是 ODT 啦），如果一个节点附上一个值，只有节点第一个数的$pre$ 会被修改。

考虑 ODT 的过程，每次修改有分裂和合并，若分裂的话最多增加三个节点，对于$pre$ 来说分裂和修改$pre$ 的时间复杂度是基本一样的（不知道为啥看上面），我们最多添加$m$ 个节点，初始最多$n$ 个，于是修改次数最多就是$O(n+m)$。

那么这样我们就可以找到$pre$ 数组被修改的位置，记录一下修改的时间，暴力单点修改就可以了，怎么找？直接上ODT，怎么求$pre$ ? 对每个颜色开ODT！。

不对啊你不说ODT被卡了吗，我们这里是求操作序列，不是直接用ODT求解，我们最后求解用的还是 CDQ 分治大神。

你疯啦开那么多 ODT？卡卡空间就可以了，离散化之后不会有很多的颜色。

但是这个空间很难受，我卡了50次才卡过。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2e6,MC=3e5,MK=1e5+15;
struct Node{
    int op,l,r,t,id;
}q[MN];
int n,m,tot,qtot,ptot,mptot,ans[MN],lst[MN],pre[MK],a[MK];
map<int,int> mp;

struct BIT{
    int t[MK];

    int lowbit(int x){
        return x&-x;
    }

    void update(int x,int k){
        while(x<MN){
            t[x]+=k;
            x+=lowbit(x);
        }
    }

    int query(int x){
        int ret=0;
        while(x){
            ret+=t[x];
            x-=lowbit(x);
        }
        return ret;
    }

}bit;

struct ODTNode{
    int l,r,val;
    bool operator<(const ODTNode &x)const{
        return l<x.l;
    }
};

struct ODT{
    set<ODTNode> s,col[MC];

    auto insert(int l,int r,int k){
        col[k].insert({l,r,k});
        return s.insert({l,r,k}).first;
    }

    void del(int l,int r,int k){
        col[k].erase({l,r,k});
        s.erase({l,r,k});
    }

    auto split(int x){
        auto it=s.lower_bound({x,0,0});
        if(it!=s.end()&&it->l==x) return it;
        it--;
        int l=it->l,r=it->r,k=it->val;
        del(l,r,k);
        insert(l,x-1,k);
        return insert(x,r,k);
    }

    int getpre(int x){
        auto it=s.upper_bound({x,0,0});
        it--;
        if(it->l<x) return x-1;
        else{
            auto co = col[it->val].lower_bound({ x, 0, 0 });
            if (co != col[it->val].begin()) return (--co)->r;
            return 0;
        }
    }

    void Assign(int l, int r, int v, int t) {
        auto itr = split(r + 1), itl = split(l);
        vector<int> ps;
        for (auto it = itl; it != itr; it++) {
            if (it != itl) ps.emplace_back(it->l);
            auto nxt = col[it->val].upper_bound(*it);
            if (nxt != col[it->val].end()) ps.emplace_back(nxt->l);
            col[it->val].erase(*it);
        }
        s.erase(itl, itr);
        insert(l, r, v);
        ps.emplace_back(l);
        auto nxt = col[v].upper_bound({ l, r, v });
        if (nxt != col[v].end()) ps.emplace_back(nxt->l);
        for (int i = 0; i < ps.size(); i++) {
            q[++qtot] = { -1,ps[i], pre[ps[i]], t, 0 };
            pre[ps[i]] = getpre(ps[i]);
            q[++qtot] = { 1,ps[i], pre[ps[i]], t, 0 };
        }
    }

}odt;

bool cmp1(Node x,Node y){
    if(x.t==y.t){
        return x.id<y.id;
    }
    return x.t<y.t;
}

bool cmp2(Node x,Node y){
    if(x.l==y.l)return x.id<y.id;
    return x.l<y.l;
}

void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    // sort(q+l+1,q+mid+1,cmp2);
    // sort(q+mid+1,q+r+1,cmp2);
    int i=l,j=mid+1;
    while(j<=r){
        while(q[i].l<=q[j].l&&i<=mid){
            if(!q[i].id) bit.update(q[i].r+1,q[i].op);
            // tmp[ttot++]=q[i++];
            i++;
        }
        if(q[j].id) ans[q[j].id]+=q[j].op*bit.query(q[j].r+1);
        // tmp[ttot++]=q[j++];
        j++;
    }
    for(int p=l;p<i;p++){
        if(!q[p].id) bit.update(q[p].r+1,-q[p].op);
    }
    // while(i<=mid) tmp[ttot++]=q[i++];
    // for(int p=l;p<=r;p++) q[p]=tmp[p];
    inplace_merge(q+l,q+mid+1,q+r+1,cmp2);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!mp[a[i]]) mp[a[i]]=++mptot;
        a[i]=mp[a[i]];
        pre[i]=lst[a[i]];
        lst[a[i]]=i;
        q[++qtot]={1,i,pre[i],0,0};
        odt.insert(i,i,a[i]);
    }
    for(int i=1;i<=m;i++){
        int op,l,r,d;
        cin>>op>>l>>r;
        if(op==1){
            cin>>d;
            if(!mp[d]) mp[d]=++mptot;
            d=mp[d];
            odt.Assign(l,r,d,i);
        }else{
            q[++qtot]={1,r,l-1,i,++tot};
            q[++qtot]={-1,l-1,l-1,i,tot};
        }
    }
    stable_sort(q+1,q+1+qtot,cmp1);//归并排序防炸空间
    cdq(1,qtot);
    for(int i=1;i<=tot;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

1.4 基于决策单调性的DP优化。

我们在讲四边形不等式优化DP做法的时候，我们给出了两个解法，一个是单调队列，另一个就是分治。

但是这个到底是什么分治？其实就是CDQ分治啦。

对于1D/1D 转移方程如下：

$$f(i)=min/max\left\{g(j)+w(i,j) \right\}\quad 1\le j < i$$

其中有决策单调性即$w(i,j)$ 满足四边形不等式或反四边形不等式，这里$g$ 可以为$f$。

若转移方程是$g+w \rightarrow f$ 的转移，且$g$ 与$f$ 的计算无关，也就是说转移是由一个已知的函数或这$f$的上一层转移过来，那么我们就可以用 CDQ 分治的方法，这种决策是离线的，我们不依赖$f_{i-1}$来计算$f_i$，这时候就不必采用单调队列这种顺序计算$f_i$了，只需要分治就可以，编码更简单也更灵活。

算法步骤：

1. 初始化：首先暴力遍历$j\in[1,n/2)$来计算$p_{n/2}$，作为分治的中心点。
2. 分治求解：接下来分别计算2个区间$[1,n/2)$和$(n/2,2]$的$p_i$。
   • 对于前半段，最优决策点一定在$[1,p_{n/2}]$之间。
   • 对于后半段，最优决策点一定在$[p_{n/2},p_n]$之间。
3. 递归处理即可。

代码实现如下：

int clac(int i,int j); //计算选择决策j的费用
// l,r是决策区间，kl,kr是决策点的区间
void dfs(int l,int r,int kl,int kr){
	int mid=(l+r)>>1,k=kl;
	for(int i=kl;i<=min(kr,mid-1);i++){
		//求费用最少的f[mid]最优决策点
		if(clac(mid,i)<clac(mid,k)) k=i;
		f[mid]=clac(mid,k);
	}
	if(l<mid) dfs(l,mid-1,kl,k);
	if(r>mid) dfs(mid+1,r,k,kr);
}

//ans=f[n];

这个的证明和基于时间分治的证明类似，这里不给出了。

2. 整体二分

2.1 基于值域的整体二分

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

我们考虑一下这个问题：

给定长度为$n$ 的序列$a$，求序列$a$ 中第$k$ 小的数。

这题怎么做都可以，我们可以考虑一个二分答案的做法。

先从小到大排序，二分答案，设当前二分值域的值为$mid$，统计序列中有多少个数$\le mid$，记为$cnt$。

• 若$k \le cnt$，那么$ans\in [l,mid]$，直接二分即可。
• 若$k>cnt$，那么$ans\in [mid+1,r]$，等价于在值域$[mid+1,r]$ 找第$k-cnt$ 小的数，那么直接$k-=cnt$ 让后直接在右半区间继续二分。

这样时间复杂度为$O(n\log |V|)$ ，其中$V$ 为值域。

如果我们加强一下呢？

给定长度为$n$ 的序列$a$，给定$m$ 次询问，每次询问区间$[l,r]$ 的中第$k$ 小的数。

这题我会，主席树吗。
我们看看怎么用整体二分来写。

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

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

代码如下：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=4e5+15,INF=1e9,MK=2e5+15;
struct Query{
    int x,y,z,id;
}q[MN],lq[MN],rq[MN];
int n,m,qtot,a[MK],ans[MK];

struct BIT{
    int t[MK];

    int lowbit(int x){
        return x&-x;
    }

    int query(int x){
        int ret=0;
        while(x){
            ret+=t[x];
            x-=lowbit(x);
        }
        return ret;
    }

    void update(int x,int k){
        while(x<MN){
            t[x]+=k;
            x+=lowbit(x);
        }
    }

}bit;

void solve(int l,int r,int st,int ed){
    if(st>ed) return;
    if(l==r){
        for(int i=st;i<=ed;i++){
            if(q[i].id) ans[q[i].id]=l;
        }
        return;
    }
    int mid=(l+r)>>1,lt=0,rt=0;
    for(int i=st;i<=ed;i++){
        if(q[i].id==0){
            if(q[i].y<=mid){
                bit.update(q[i].x,1);
                lq[++lt]=q[i];
            }else rq[++rt]=q[i];
        }else{
            int cnt=bit.query(q[i].y)-bit.query(q[i].x-1);
            if(cnt>=q[i].z) lq[++lt]=q[i];
            else q[i].z-=cnt,rq[++rt]=q[i];
        }
    }
    for(int i=ed;i>=st;i--) if(q[i].id==0&&q[i].y<=mid) bit.update(q[i].x,-1);
    for(int i=1;i<=lt;i++) q[st+i-1]=lq[i];
    for(int i=1;i<=rt;i++) q[st+lt+i-1]=rq[i];
    solve(l,mid,st,st+lt-1);
    solve(mid+1,r,st+lt,ed);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        q[++qtot]={i,a[i],0,0};
    }
    for(int i=1;i<=m;i++){
        int l,r,k;
        cin>>l>>r>>k;
        q[++qtot]={l,r,k,i};
    }
    solve(-INF,INF,1,qtot);
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

2.2 例题

P1527 [国家集训队] 矩阵乘法

二维树状数组即可，这个真的没什么好讲的，注意一下求一个矩阵点要容斥一下。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=520,MQ=5e5+15,INF=1e9+7;
struct Query{
    int x1,y1,x2,y2,k,id;
}q[MQ],lq[MQ],rq[MQ];
int n,m,qtot,atot,tot,ans[MQ],a[MN];
struct ewBIT{
    int t[MN][MN];

    int lowbit(int x){
        return x&-x;
    }

    void update(int x,int y,int k){
        for(int i=x;i<MN;i+=lowbit(i)){
            for(int j=y;j<MN;j+=lowbit(j)){
                t[i][j]+=k;
            }
        }
    }

    int query(int x,int y){
        int ret=0;
        for(int i=x;i;i-=lowbit(i)){
            for(int j=y;j;j-=lowbit(j)){
                ret+=t[i][j];
            }
        }
        return ret;
    }

}bit;

void solve(int l,int r,int st,int ed){
    if(st>ed) return;
    if(l==r){
        for(int i=st;i<=ed;i++){
            ans[q[i].id]=l;
        }
        return;
    }
    int mid=(l+r)>>1,lt=0,rt=0;
    for(int i=st;i<=ed;i++){
        if(!q[i].id){
            if(q[i].k<=mid) bit.update(q[i].x1,q[i].y1,1),lq[++lt]=q[i];
            else rq[++rt]=q[i];
        }else{
            int cnt=bit.query(q[i].x2,q[i].y2)-bit.query(q[i].x2,q[i].y1-1)-bit.query(q[i].x1-1,q[i].y2)+bit.query(q[i].x1-1,q[i].y1-1);
            if(cnt>=q[i].k) lq[++lt]=q[i];
            else q[i].k-=cnt,rq[++rt]=q[i];
        }
    }
    for(int i=ed;i>=st;i--) if(!q[i].id&&q[i].k<=mid) bit.update(q[i].x1,q[i].y1,-1);
    for(int i=1;i<=lt;i++) q[st+i-1]=lq[i];
    for(int i=1;i<=rt;i++) q[st+lt+i-1]=rq[i];
    solve(l,mid,st,st+lt-1);
    solve(mid+1,r,st+lt,ed);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x;
            cin>>x;
            q[++qtot]={i,j,0,0,x,0};
            a[++tot]=x;
        }
    }
    for(int i=1;i<=m;i++){
        int x1,y1,x2,y2,k;
        cin>>x1>>y1>>x2>>y2>>k;
        q[++qtot]={x1,y1,x2,y2,k,i};
    }
    solve(-INF,INF,1,qtot);
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

P4602 [CTSC2018] 混合果汁

发现询问独立，答案可二分，并且可离线，考虑整体二分。

我们实际上二分美味度，将美味度大于等于$mid$ 的果汁搞出来，按照单价从小到大，求买$L_i$ 升的价格。我们可以用树状数组维护单价，二分树状数组求得最大单价$p$ 使得单价不大于$p$ 的果汁体积$L<L_i$，买单价不大于$p$ 的果汁和$L_i-L$ 升单价为$p$ 的果汁即可。

树状数组二分可以倍增写，注意每次递归前要把美味度小于$L$ （这里$L$ 是值域的 L）已经加入树状数组，这样才能保证复杂度仅与$R-L$ 相关。

时间复杂度$O((n+m \log^2 (n+m)))$。