前言

我将通过这篇和以前的三篇创作计划讲解洛谷绝大多数的 CDQ 分治和整体二分题目，至于主席树别管。

喜报：我在 P3332 [ZJOI2013] K 大数查询 中跑到了次优解，但是帅童把我的代码改了改进行测试把我挤下去，总之记得这题是 me 的次优解。

闲话：

对于来刷无用评论的人：

接下来就切入正题吧。

一、一些主席树例题

先来几道简单的主席树题目开开胃。
P1383 高级打字机
一眼栈模拟
但是仔细看一看题面：

对于前 $50\%$ 的数据，保证 Undo 操作不会撤销 Undo 操作。

也就是说，对于另外 $50\%$ 的数据， Undo 操作是会撤销 Undo 操作的。
那么这时候该如何解决呢？
本题中的修改操作只有一个，而 Undo 操作只会影响 Undo 和 Type. 也就是说，如果每次 Undo 和 Type 算作一个新版本，我们可以在 Undo 时直接跳回以前的版本。很容易想到可以用可持久化数据结构来完成。由于可持久化线段树最简单，所以我们可以使用可持久化线段树。把所有字母存在主席树的叶子节点即可。

接下来我们想想每个操作要如何实现：Type 操作要放到文本的结尾，我们可以在主席树上维护一个 sz 数组，代表每个节点的子树有多少个叶子节点存了字母，在 Type 时二分出当前文本的结尾并在结尾进行 update. Undo 操作是回溯，可以直接用主席树的 root 数组实现。主席树的 root 数组存了不同版本的线段树其根节点在结构体数组中的下标，当我们要把当前版本回溯时直接新开一个版本然后把根节点设为要回溯的那个版本就行了。Query 是简单的主席树上二分查找。

Type 操作和 Query 操作时间复杂度是 $O(\log N)$ ，Undo 操作的时间复杂度是 $O(1)$.

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define enter putchar_unlocked('\n')
#define mid (pl+pr>>1)
#define say putchar_unlocked
int n,root[100005],cnt,tot,x2;
char op,x;
struct hjt{int l,r,sz;char x;}t[2000005];
void modify(int pre,int &cur,int pl,int pr,char c){
    t[cur=++cnt]=t[pre];
    if(pl==pr){t[cur].sz=1,t[cur].x=c;return;}
    if(t[t[pre].l].sz==mid-pl+1)modify(t[pre].r,t[cur].r,mid+1,pr,c);
    else modify(t[pre].l,t[cur].l,pl,mid,c);
    t[cur].sz=t[t[cur].l].sz+t[t[cur].r].sz;
}
char query(int cur,int pl,int pr,int x){
    if(pl==pr)return t[cur].x;
    if(t[t[cur].l].sz<x)return query(t[cur].r,mid+1,pr,x-t[t[cur].l].sz);
    return query(t[cur].l,pl,mid,x);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read();
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(int i=1;i<=n;++i){
        cin>>op;
        if(op=='T')cin>>x,++tot,modify(root[tot-1],root[tot],1,n,x);
        else if(op=='U')cin>>x2,++tot,root[tot]=root[tot-x2-1];
        else cin>>x2,say(query(root[tot],1,n,x2)),enter;
    }
    return 0;
}

（cin 真香）
下一道

P6166 [IOI 2012] scrivener
这题和上一题简直一模一样，甚至前两个操作的输入都是一样的。但是此题的数据量非常野（主席树：我跑 $10^6$ 吗？）。而且不愧是 IOI, 样例也是真的大方。

所以你把空间改了改就交上去了吗？

讨论区的大佬们热情地分享了卡常经验：1.可以不开 long long. 2.可以不存左右儿子，让左右儿子跟着函数递归。由于我太蒟蒻了不会后者，开了个 int 卡线过了这一题。

#include<bits/stdc++.h>
using namespace std;
#define enter putchar_unlocked('\n')
#define mid (pl+pr>>1)
#define say putchar_unlocked
int n,root[1000005],cnt,tot,x2;
char op,x;
struct hjt{int l,r,sz;char x;}t[20000005];
void modify(int pre,int &cur,int pl,int pr,char c){
    t[cur=++cnt]=t[pre];
    if(pl==pr){t[cur].sz=1,t[cur].x=c;return;}
    if(t[t[pre].l].sz==mid-pl+1)modify(t[pre].r,t[cur].r,mid+1,pr,c);
    else modify(t[pre].l,t[cur].l,pl,mid,c);
    t[cur].sz=t[t[cur].l].sz+t[t[cur].r].sz;
}
char query(int cur,int pl,int pr,int x){
    if(pl==pr)return t[cur].x;
    if(t[t[cur].l].sz<x)return query(t[cur].r,mid+1,pr,x-t[t[cur].l].sz);
    return query(t[cur].l,pl,mid,x);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read();
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(int i=1;i<=n;++i){
        cin>>op;
        if(op=='T')cin>>x,++tot,modify(root[tot-1],root[tot],1,n,x);
        else if(op=='U')cin>>x2,++tot,root[tot]=root[tot-x2-1];
        else cin>>x2,say(query(root[tot],1,n,x2+1)),enter;
    }
    return 0;
}

热完身了吗？看看一些紫题。

P3293 [SCOI2016] 美味

前置知识：0-1 Trie 求最大（小）异或值。这个应该所有人都会了，但是这里怕你们说我不负责讲一讲。0-1 Trie 把存进去的每个整数由高位向低位存储二进制值，前面没有就补齐 0。当需要在 Trie 存储的数中找到一个使它与给定数的异或值最大时，从高到低位遍历给定数并从根节点遍历 Trie. 如果当前位为 0 就寻找 Trie 的当前节点有没有值为 1 的儿子，否则查找有没有值为 0 的儿子（与给定数正好相反）。如果有就递归与原数相反的位，否则就只能递归另一个位了。这个贪心确保了最高位的值。

此题只是加了一个 $x_i$. 怎么做呢？依旧遍历 $b_i$ 的位。如果是 1，我们希望能找到一个此位为 0 的 $a_i$. 如图：

我们要找最小 a 和最大 a 之间有没有值。注意到最小 a 正好就是当前的 ans, 最大值可以算出是 $ans+2^i-1$ ，其中 i 是当前位到最右端的距离。

于是我们只需要求在两个区间 $[l,r]$ 和 $[ans,ans+2^i-1]$ 的约束条件下有没有值即可。如果 b 的当前位是 0，我们也可以计算出对应的左右端点，答案区间为 $[ans-x+(1<<i),ans-x+(1<<(i+1))]$, 可以自己对照上图画一个图（1000...~1111...）。有两个区间的约束条件，考虑主席树。下面的主席树使用了一种类似 0-1 Trie 的存储方法，但其实和主席树的普通写法是一样的。我原先是求具体有多少个值再判断，但是这个玩意似乎可以直接返回 bool 值然后通过短路的性质优化。于是我就从 2.50s 加速到了 1.80s.

Code:

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define mid (l+r>>1)
#define k (sum[v]-sum[u])
#define enter putchar_unlocked('\n')
int n,m,N,a[500005],cnt,t[9000005],ch[9000005][2],sum[9000005],b,x,l,r,ans;
void update(int pre,int &cur,int l,int r,int x){
    cur=++cnt,ch[cur][0]=ch[pre][0],ch[cur][1]=ch[pre][1],sum[cur]=sum[pre]+1;
    if(l==r)return;
    if(mid>=x)update(ch[pre][0],ch[cur][0],l,mid,x);
    else update(ch[pre][1],ch[cur][1],mid+1,r,x);
}
bool qry(int u,int v,int l,int r,int L,int R){
    if(R<l||L>r||!k)return 0;
    if(L<=l&&r<=R)return 1;
    return (bool)qry(ch[u][0],ch[v][0],l,mid,L,R)||(bool)qry(ch[u][1],ch[v][1],mid+1,r,L,R);
}
il int read(){
    re int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
il void write(int x){
    x<0?x=-x,putchar_unlocked('-'):0;static short st[50],top(0);
    do st[++top]=x%10,x/=10;while(x);
    while(top)putchar_unlocked(st[top--]|48);
}
signed main(){
    n=read(),m=read();
    for(re int i=1;i<=n;++i)N=max(N,a[i]=read());
    for(re int i=1;i<=n;++i)update(t[i-1],t[i],0,N,a[i]);
    while(m--){
        b=read(),x=read(),l=read(),r=read(),ans=0;
        for(re int i=18;i>=0;--i){
            ans+=(1<<i)*(int)(b&(1<<i)&&!qry(t[l-1],t[r],0,N,ans-x,ans-x+(1<<i)-1));
            ans+=(1<<i)*(int)(!(b&(1<<i))&&qry(t[l-1],t[r],0,N,ans-x+(1<<i),ans-x+(1<<(i+1))-1));
        }
        write(ans^b),enter;
    }
    return 0;
}

P4735 最大异或和 是一道类似的题，但是主要是通过可持久化 Trie 或者离线 Trie 实现，基本上是模板题。可持久化 Trie 和主席树相似，都是通过函数式编程实现可持久化。下面给出代码，请自主练习其它例题。

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define enter putchar_unlocked('\n')
il int read(){
    re int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
il void write(int x){
    x<0?x=-x,putchar_unlocked('-'):0;
    static short st[50],top(0);
    do st[++top]=x%10,x/=10;while(x);
    while(top)putchar_unlocked(st[top--]|48);
}
int n,m,rt[600005],cnt[15000005],t[15000005][2],pre[600005],tot;
char s[5];
il void ins(int a,int b,int k,int x){
    if(k<0)return;
    bool i=(x>>k)&1;
    t[a][!i]=t[b][!i];
    t[a][i]=++tot;
    cnt[t[a][i]]=cnt[t[b][i]]+1;
    ins(t[a][i],t[b][i],k-1,x);
}
il int qry(int a,int b,int k,int x){
    if(k<0)return 0;
    bool i=(x>>k)&1;
    if(cnt[t[b][!i]]>cnt[t[a][!i]])return (1<<k)+qry(t[a][!i],t[b][!i],k-1,x);
    else return qry(t[a][i],t[b][i],k-1,x);
}
signed main(){
    n=read(),m=read(),ins(rt[0]=tot=1,0,25,0);
    for(re int i=1;i<=n;++i)pre[i]=pre[i-1]^read(),rt[i]=++tot,ins(rt[i],rt[i-1],25,pre[i]);
    for(re int i=1;i<=m;++i){
        scanf("%s",s);
        if(s[0]=='A')++n,pre[n]=pre[n-1]^read(),rt[n]=++tot,ins(rt[n],rt[n-1],25,pre[n]);
        else{int i=read()-1,j=read()-1,b=read();write(qry((i)?rt[i-1]:0,rt[j],25,pre[n]^b)),enter;}
    }
    return 0;
}

二、各种整体二分

树上整体二分

我们前面讲过的整体二分都是在序列上通过数据结构维护的。如果在树上呢？我们似乎可以通过树链剖分达到树上链和统计的效果，但是这样每次修改时间复杂度是 $O(\log ^2N)$ ，整体二分就变成路边一条了。有没有更快的方法？

给出一道模板。

P4216 [SCOI2015] 情报传递

主要的思路略。由于危险值随时间增加，直接把 i 次询问危险值是否大于等于 k 转化为 1~i-k-1 的时间段有几个点有任务出现，离线处理将每个时间点的询问加入 vector, 然后对应地在树上查询。求多少个人接手是简单的树上差分求链长度。

这里主要讲讲怎么实现高效的树上单点修改和链上和查询。我们先做一次 DFS ，求出每一个节点的入序 st 和出序 ed. 入序可以在 DFS 到这个节点时直接设为 ++cnt, 出序就是在 DFS 完它的子树之后的 cnt. 如果把 $sz_i$ 定义为节点 i 的子树大小则 $ed_i=st_i+sz_i-1$. 如果将叶子节点的出序设为入序，对于其它节点则求子树上的最大出序也是可以的。如下图，蓝表入序，红表出序：

将入序作为树状数组的下标，即可做到单点修改和根节点到给定节点这条链上的权值和。

当节点 u 的权值增加 v 时，将树状数组中区间 $[st_u,ed_u]$ 这个区间进行区间增加 v 的操作。查询根节点到给定节点 u 这条链上的权值和（设为 $\operatorname{pre}_u$)，$\operatorname{pre}_u$ 即是所维护的树状数组上 $st_u$ 这个点的权值。为什么呢？我们需要证明当且仅当 u 是 v 的祖先时，$st_v\in [st_u,ed_u]$. 求入序的 DFS 是从根节点往下的，因此 u 的子树上所有节点的入序都大于等于 $st_u$, 根据 $ed_u$ 的定义，u 的子树上最大的 $st$ 值小于等于 $ed_u$. 因此当 u 是 v 的祖先时，对 u 的修改必定对 v 造成贡献。而如果 u 不是 v 的祖先，如果 u 的遍历顺序在 v 之前，有 $ed_u < st_v$, 否则有 $st_u > st_v$, 贡献不会计算给 v.

有了神器之后开始利用。我们计算了 $\operatorname{pre}$ 值之后可以进行树上差分，设 $\operatorname{lca}_{u,v}$ 为 u 和 v 的最近公共祖先，$fa_u$ 为 u 的父亲节点，则 u 到 v 这条链的权值和为 $\operatorname{pre}_u+\operatorname{pre}_v-\operatorname{pre}_{\operatorname{lca}_{u,v}}-\operatorname{pre}_{fa_{\operatorname{lca}_{u,v}}}$. 于是我们就实现了 $O(\log N)$ 的树上单点修改和链上和查询。本题代码如下：

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
int n,m,tree[200005],head[200005],sz[200005],son[200005],top[200005],dep[200005],fa[200005],id[200005],ttl,cnt,op[200005],x[200005],y[200005],c[200005],ans[200005];
vector<int>tasks[200005];
struct node{int v,nxt;}t[400005];
void add(int x,int d){for(;x<=n;x+=x&-x)tree[x]+=d;}
int qry(int x){int res=0;for(;x;x^=x&-x)res+=tree[x];return res;}
void link(int x,int y){t[++cnt]={y,head[x]},head[x]=cnt,t[++cnt]={x,head[y]},head[y]=cnt;}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
void dfs1(int u,int lst){
    dep[u]=dep[lst]****z[u]=1,fa[u]=lst,id[u]=++ttl;
    for(int i=head[u];i;i=t[i].nxt)
        if(t[i].v^lst){
            dfs1(t[i].v,u);
            sz[u]+=sz[t[i].v];
            if(sz[t[i].v]>sz[son[u]])son[u]=t[i].v;
        }
}
void dfs2(int u,int topx){
    top[u]=topx;
    if(son[u])dfs2(son[u],topx);
    for(int i=head[u];i;i=t[i].nxt)
        if(t[i].v^fa[u]&&t[i].v^son[u])dfs2(t[i].v,t[i].v);
}
int lca(int u,int v){
    while(top[u]^top[v])dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
    return dep[u]<dep[v]?u:v;
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i)link(i,read());
    dfs1(1,0),dfs2(1,1),m=read();
    for(int i=1;i<=m;++i){
        op[i]=read();
        if(op[i]==1){x[i]=read(),y[i]=read(),c[i]=read();if(c[i]<i)tasks[i-c[i]-1].push_back(i);}
        else x[i]=read();
    }
    for(int i=1;i<=m;++i){
        if(op[i]==2)add(id[x[i]],1),add(id[x[i]]+sz[x[i]],-1);
        for(int j:tasks[i]){int xyl=lca(x[j],y[j]);ans[j]=qry(id[x[j]])+qry(id[y[j]])-qry(id[xyl])-qry(id[fa[xyl]]);}
        if(op[i]==1)write(dep[x[i]]+dep[y[i]]-(dep[lca(x[i],y[i])]<<1)+1),putchar_unlocked(' '),write(ans[i]),putchar_unlocked('\n');
    }
    return 0;
}

真正的树上整体二分：P4175 [CTSC2008] 网络管理

这是一道简单的树上整体二分，但是我又饭堂了写了很多遍才过。

树上静态查询链上第 k 小值我在上一篇创作计划中已经讲过了，使用了树上主席树。但是如果需要修改，很明显需要树套树，而 Xylophone 自古以来就没写过树套树。考虑整体二分。

有了 DFN 序树状数组的加持这题对你们来说应该比呼吸还简单，依旧带修区间第 k 小模板，只是把树状数组修改的下标变了一下，每次查询查链条上被标记的数有多少而已。

这些题可以用 Tarjan 或者其它算法提前储存 $\operatorname{LCA}$, 但是太麻烦蒟蒻不会实现直接疯狂剖剖剖。

Code:

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
int n,m,tree[160005],head[80005],sz[80005],son[80005],top[80005],dep[80005],fa[80005],ans[80005],ru[80005],chu[80005],ct,tot,ttl,qcnt,a[80005],cnt;
struct node{int v,nxt;}t[160005];
struct xyl{int op,x,y,z,id;}q[240005],q1[240005],q2[240005];
void add(int x,int d){for(;x<=n;x+=x&-x)tree[x]+=d;}
void clr(int x){for(;x<=n&&tree[x];x+=x&-x)tree[x]=0;}
int qry(int x){int res=0;for(;x;x^=x&-x)res+=tree[x];return res;}
void link(int x,int y){t[++ct]={y,head[x]},head[x]=ct,t[++ct]={x,head[y]},head[y]=ct;}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
void dfs1(int u,int lst){
    dep[u]=dep[lst]****z[u]=1,fa[u]=lst,ru[u]=++ttl;
    for(int i=head[u];i;i=t[i].nxt)
        if(t[i].v^lst){
            dfs1(t[i].v,u);
            sz[u]+=sz[t[i].v];
            if(sz[t[i].v]>sz[son[u]])son[u]=t[i].v;
        }
    chu[u]=ttl;
}
void dfs2(int u,int topx){
    top[u]=topx;
    if(son[u])dfs2(son[u],topx);
    for(int i=head[u];i;i=t[i].nxt)
        if(t[i].v^fa[u]&&t[i].v^son[u])dfs2(t[i].v,t[i].v);
}
int lca(int u,int v){
    while(top[u]^top[v])dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
    return dep[u]<dep[v]?u:v;
}
void solve(int ql,int qr,int l,int r){
    if(ql>qr)return;
    if(l==r){
        for(int i=ql;i<=qr;++i)if(q[i].op==2)ans[q[i].id]=l;
        return;
    }
    int cnt1=0,cnt2=0;bool b1=0,b2=0;
    for(int i=ql;i<=qr;++i){
        if(q[i].op==2){
            int lc=lca(q[i].y,q[i].z),k=qry(ru[q[i].y])+qry(ru[q[i].z])-qry(ru[lc])-qry(ru[fa[lc]]);
            if(q[i].x<=k)q1[++cnt1]=q[i],b1=1;
            else q[i].x-=k,q2[++cnt2]=q[i],b2=1;
        }
        else{
            if(q[i].y<=mid)add(ru[q[i].x],q[i].z),add(chu[q[i].x]+1,-q[i].z),q1[++cnt1]=q[i];
            else q2[++cnt2]=q[i];
        }
    }
    for(int i=ql;i<=qr;++i)if(q[i].op^2&&q[i].y<=mid)clr(ru[q[i].x]),clr(chu[q[i].x]+1);
    for(int i=1;i<=cnt1;++i)q[ql+i-1]=q1[i];
    for(int i=1;i<=cnt2;++i)q[ql+cnt1+i-1]=q2[i];
    if(b1)solve(ql,ql+cnt1-1,l,mid);
    if(b2)solve(ql+cnt1,qr,mid+1,r);
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)q[++cnt]={1,i,1e8-read(),1,0},a[i]=1e8-q[i].y;
    for(int i=1;i<n;++i)link(read(),read());
    dfs1(1,0),dfs2(1,1);
    for(int i=1,k;i<=m;++i){
        k=read();
        if(k)q[++cnt]={2,k,read(),read(),++qcnt};
        else{
            int s=read(),t=read();
            q[++cnt]={1,s,1e8-a[s],-1,0};
            a[s]=t;
            q[++cnt]={1,s,1e8-a[s],1,0};
        }
    }
    solve(1,cnt,0,100000001);
    for(int i=1;i<=qcnt;++i){if(ans[i]^100000001)write(1e8-ans[i]),putchar_unlocked('\n');else puts("invalid request!");}
    return 0;
}

P3250 [HNOI2016] 网络

请求的给出和撤销都是整体二分的基本操作。实现链条的修改和单点查询只需要进行简单的树上差分即可。某个服务器出现故障时让你查询这个服务器没影响到的请求的重要度最大值，而且这个题目良心地在每次服务器出问题之后立刻修复，所以 3 操作完全可以看作整体二分的查询。然后把 1，2 操作看作修改，二分答案求重要度最大值，设当前二分到 mid, 执行所有重要度大于等于 mid 的链上修改操作，查询时查询单点权值，并与修改总和进行比较，如果等于总和就说明所有重要度大于等于 mid 的请求都要经过这个点，于是 mid 就美酒了，否则这个查询就悠久。这题也能提前存 $\operatorname{LCA}$, 不过我又没有存。

Code：

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
#define st (q[i].op?-1:1)
int n,m,tree[100005],head[100005],sz[100005],son[100005],top[100005],dep[100005],fa[100005],ans[200005],ru[100005],chu[100005],ct,tot,ttl,U[200005],V[200005],W[200005],qcnt;
struct node{int v,nxt;}t[200005];
struct xyl{int op,x,id;}q[300005],q1[300005],q2[300005];
void add(int x,int d){for(;x<=n;x+=x&-x)tree[x]+=d;}
int qry(int x){int res=0;for(;x;x^=x&-x)res+=tree[x];return res;}
void link(int x,int y){t[++ct]={y,head[x]},head[x]=ct,t[++ct]={x,head[y]},head[y]=ct;}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
void dfs1(int u,int lst){
    dep[u]=dep[lst]****z[u]=1,fa[u]=lst,ru[u]=++ttl;
    for(int i=head[u];i;i=t[i].nxt)
        if(t[i].v^lst){
            dfs1(t[i].v,u);
            sz[u]+=sz[t[i].v];
            if(sz[t[i].v]>sz[son[u]])son[u]=t[i].v;
        }
    chu[u]=ttl;
}
void dfs2(int u,int topx){
    top[u]=topx;
    if(son[u])dfs2(son[u],topx);
    for(int i=head[u];i;i=t[i].nxt)
        if(t[i].v^fa[u]&&t[i].v^son[u])dfs2(t[i].v,t[i].v);
}
int lca(int u,int v){
    while(top[u]^top[v])dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
    return dep[u]<dep[v]?u:v;
}
void modify(int x,int y,int v){
    int k=lca(x,y);
    add(ru[x],v),add(ru[y],v),add(ru[k],-v);
    if(fa[k])add(ru[fa[k]],-v);
}
void solve(int ql,int qr,int l,int r){
    if(ql>qr)return;
    if(l==r){
        for(int i=ql;i<=qr;++i)if(q[i].op==2)ans[q[i].id]=l;
        return;
    }
    int cnt=0,cnt1=0,cnt2=0;bool b1=0,b2=0;
    for(int i=ql;i<=qr;++i){
        if(q[i].op==2){
            int k=qry(chu[q[i].x])-qry(ru[q[i].x]-1);
            if(k^cnt)q2[++cnt2]=q[i],b2=1;
            else q1[++cnt1]=q[i],b1=1;
        }
        else{
            if(W[q[i].x]<=mid)q1[++cnt1]=q[i];
            else cnt+=st,modify(U[q[i].x],V[q[i].x],st),q2[++cnt2]=q[i];
        }
    }
    for(int i=1;i<=cnt2;++i)if(q2[i].op^2)modify(U[q2[i].x],V[q2[i].x],q2[i].op?1:-1);
    for(int i=1;i<=cnt1;++i)q[ql+i-1]=q1[i];
    for(int i=1;i<=cnt2;++i)q[ql+cnt1+i-1]=q2[i];
    if(b1)solve(ql,ql+cnt1-1,l,mid);
    if(b2)solve(ql+cnt1,qr,mid+1,r);
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<n;++i)link(read(),read());
    dfs1(1,0),dfs2(1,1);
    for(int i=1;i<=m;++i){
        q[i].op=read(),q[i].id=q[i].op^2?0:++qcnt;
        if(!q[i].op)U[i]=read(),V[i]=read(),W[i]=read(),q[i].x=i;
        else q[i].x=read();
    }
    solve(1,m,-1,1e9);
    for(int i=1;i<=qcnt;++i)write(ans[i]),putchar_unlocked('\n');
    return 0;
}

扫描线整体二分（偏序整体二分）

P3242 [HNOI2015] 接水果

这是一道极好的神仙题，除了博弈论几乎没有任何其它题的思维有这题巧妙，其天才般的思想和知识点间美妙的融合让所有 OIer 叹为观止。确切地说，这是我此生见过的最巧妙的题，整体二分的实现也不由得让人对出题者产生由衷的钦佩。

注意到这居然是省选题。注意到我不知道风见幽香是谁。注意到这题居然是用盘子接水果而不是水果接盘子，盘子要被水果包含才能装住水果。

树上第 k 小，考虑整体二分，因为我们这篇的标题中整体二分排在最前面。假设我们的盘子是以下蓝色链条，x 和 y 是盘子的两个端点，z 是 x 在盘子上的儿子，能装住盘子的水果的两个端点为 u,v, 其中 $dep_u<dep_v$（如果不是则将两个端点交换）, u 和 v 的最近公共祖先是 u：

此时图中红色的部分即是 u 可能的范围，蓝色的部分即是 v 可能的范围。

如果 u 不是 v 的祖先，则：

可贡献的图就如上所示了。因此，询问 $(x,y)$ 与 $\operatorname{lca}_{u,v}=u$ 时 $st_u\in [1,st_z)|(ed_z,N],st_v\in [st_y,ed_y]$ 和当不满足 $\operatorname{lca}_{u,v}=u$ 时 $st_u\in [st_x,ed_x],st_v\in [st_y,ed_y]$ 的果子 $(u,v)$ 有关。我们注意到这个约束条件很像是矩形，把每个盘子看作一个矩形，它能装住的所有点都是能接住的果子。问题转化为求一个点所在的所有矩形中第 $k$ 小的权值，判断时将 $[0,mid]$ 的所有矩形加一然后单点查询。可以在每次整体二分中排序，然后用扫描线求出被标记的数有多少个并进行二分。由于扫描线自带一次撤销操作，因此不用在整体二分后再清空树状数组。

这个扫描线没有面积并和周长并里的那么麻烦，只需要在扫到入边时加权，扫到出边时减回去（是个人都会做）。

Code：

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
#define re register
#define il inline
int n,m,q,t[40005],ans[40005],b[40005],tot,head[40005],to[80005],nxt[80005],cnt,ttl,id,top[40005],dep[40005],sz[40005],son[40005],fa[40005],st[40005],ed[40005],k,x,y,s,z,qcnt;
struct xyl{int op,x,l,r,k,v,id;bool operator<(const xyl&s)const{return x^s.x?x<s.x:op<s.op;}}a[200005],q1[200005],q2[200005];
il void add(int x,int d){for(;x<=n;x+=x&-x)t[x]+=d;}
il int qry(int x){re int res=0;for(;x;x^=x&-x)res+=t[x];return res;}
il void link(int x,int y){to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt,to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;}
void dfs1(int u,int lst){
    fa[u]=lst,sz[u]=1,dep[u]=dep[lst]+1;
    for(re int i=head[u];i;i=nxt[i])
        if(lst^to[i]){
            dfs1(to[i],u);
            sz[u]+=sz[to[i]];
            if(sz[to[i]]>sz[son[u]])son[u]=to[i];
        }
}
void dfs2(int u,int topx){
    top[u]=topx,st[u]=++ttl;
    if(son[u])dfs2(son[u],topx);
    for(re int i=head[u];i;i=nxt[i])
        if(to[i]^fa[u]&&to[i]^son[u])dfs2(to[i],to[i]);
    ed[u]=ttl;
}
il int lca(int x,int y){
    while(top[x]^top[y])dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
il int theson(int x,int y){
    while(top[x]^top[y]){if(fa[top[x]]^y)x=fa[top[x]];else return top[x];}
    return son[y];
}
void solve(int ql,int qr,int l,int r){
    if(ql>qr)return;
    if(l==r){
        for(re int i=ql;i<=qr;++i)
            if(a[i].op==2)ans[a[i].id]=l;
        return;
    }
    re int c1=0,c2=0;
    for(re int i=ql;i<=qr;++i){
        if(a[i].op^2){
            if(a[i].k<=mid)add(a[i].l,a[i].v),add(a[i].r+1,-a[i].v),q1[++c1]=a[i];
            else q2[++c2]=a[i];
        }
        else{
            k=qry(a[i].l);
            if(a[i].k<=k)q1[++c1]=a[i];
            else a[i].k-=k,q2[++c2]=a[i];
        }
    }
    for(re int i=1;i<=c1;++i)a[ql+i-1]=q1[i];
    for(re int i=1;i<=c2;++i)a[ql+c1+i-1]=q2[i];
    solve(ql,ql+c1-1,l,mid),solve(ql+c1,qr,mid+1,r);
}
il int read(){
    re int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
il void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked((x%10)|48);
}
signed main(){
    n=read(),m=read(),q=read();
    for(re int i=1;i<n;++i)link(read(),read());
    dfs1(1,0),dfs2(1,1);
    for(re int i=1;i<=m;++i){
        x=read(),y=read(),b[i]=s=read();
        if(st[x]>st[y])x^=y^=x^=y;
        if(lca(x,y)^x)a[++qcnt]={1,st[x],st[y],ed[y],s,1,0},a[++qcnt]={1,ed[x]****t[y],ed[y],s,-1,0};
        else{
            z=theson(y,x);
            if(st[z]>1)a[++qcnt]={1,1,st[y],ed[y],s,1,0},a[++qcnt]={1,st[z],st[y],ed[y],s,-1,0};
            if(ed[z]<n)a[++qcnt]={1,st[y],ed[z]+1,n,s,1,0},a[++qcnt]={1,ed[y]+1,ed[z]+1,n,s,-1,0};
        }
    }
    sort(b+1,b+m+1),tot=unique(b+1,b+m+1)-b-1;
    for(re int i=1;i<=qcnt;++i)a[i].k=lower_bound(b+1,b+tot+1,a[i].k)-b;
    for(re int i=1;i<=q;++i){
        x=read(),y=read(),s=read();
        if(st[x]>st[y])x^=y^=x^=y;
        a[++qcnt]={2,st[x],st[y],0,s,0,i};
    }
    sort(a+1,a+qcnt+1),solve(1,qcnt,1,tot);
    for(re int i=1;i<=q;++i)write(b[ans[i]]),putchar_unlocked('\n');
    return 0;
}

成功拿到此题最优解：

P3527 [POI 2011] MET-Meteors

本题是整体二分的经典例题之一。每个国家都是询问，如何求每个国家收到了多少陨石？可以将每个国家的领土用链式前向星存储起来，也可以用邻接表。接下来就是整体二分模板，只需要将询问对象改成国家就行了，可以用 $O(N\log ^2N)$ 的时间复杂度通过本题。本题也有一种单 $\log$ 的整体二分解法，看了一晚上没看懂放弃了，~~我好**~~看得懂的可以去学习一下。

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define mid (l+r>>1)
int read(){
    re int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>9)write(x/10);
    putchar_unlocked((x%10)|48);
}
struct xyl{int head,id,k;}q[300005],tmp[600005];
int n,m,k,a[300005],tree[600005],nxt[300005],to[300005],ans[300005],L[300005],R[300005],cnt;
void add(int x,int k){for(;x<=m<<1;x+=x&-x)tree[x]+=k;}
int sum(int x){re int res=0;for(;x;x^=x&-x)res+=tree[x];return res;}
void clr(int x){for(;tree[x]&&x<=m<<1;x+=x&-x)tree[x]=0;}
void link(int x,int y){nxt[++cnt]=q[x].head,to[cnt]=y,q[x].head=cnt;}
void solve(int l,int r,int ql,int qr){
    if(ql>qr)return;
    if(l==r){for(re int i=ql;i<=qr;++i)ans[q[i].id]=l;return;}
    int c1=0,c2=n;
    for(re int i=l;i<=mid;++i)add(L[i],a[i]),add(R[i]+1,-a[i]);
    for(re int i=ql;i<=qr;++i){
        int tm=0;
        for(int j=q[i].head;j&&tm<=q[i].k;j=nxt[j])tm+=sum(to[j])+sum(to[j]+m);
        if(tm>=q[i].k)tmp[++c1]=q[i];
        else q[i].k-=tm,tmp[++c2]=q[i];
    }
    for(re int i=l;i<=mid;++i)clr(L[i]),clr(R[i]+1);
    for(re int i=1;i<=c1;++i)q[ql+i-1]=tmp[i];
    for(re int i=n+1;i<=c2;++i)q[ql+c1+i-n-1]=tmp[i];
    solve(l,mid,ql,ql+c1-1),solve(mid+1,r,qr-c2+n+1,qr);
}
signed main(){
    n=read(),m=read();
    for(re int i=1;i<=m;++i)link(read(),i);
    for(re int i=1;i<=n;++i)q[i].id=i,q[i].k=read();
    k=read();for(re int i=1;i<=k;++i)L[i]=read(),R[i]=read(),a[i]=read(),R[i]+=(R[i]<L[i])*m;
    solve(1,k+1,1,n);
    for(re int i=1;i<=n;++i){if(ans[i]==k+1)printf("NIE\n");else write(ans[i]),putchar_unlocked('\n');}
    return 0;
}

整体二分构造单调性序列

例题：P4597 序列 sequence

很明显这是一道爵士好题，但是不给你谷题号你们应该都会搜错题（

此题有多种解法，比如下凸壳 DP，贪心，整体二分。

1.贪心

贪心操作：从左到右遍历数组，将当前数设为 x, 将以前的序列最大值设为 y. 当 $y>x$ 时，通过 -1 操作把 y 减到 x. 由于使 $x=y$ 的代价相等，因此把 y 减少是最优的。

然后就没了。

这个肯定有什么神秘的原理，下面来讲讲原理。

维护一个大根堆，设每次操作加入一个元素 x, y 为大根堆堆顶，x',y' 为修改后的 x,y. 如果 $x\ge y$ 不予操作直接将 x 加入大根堆，否则只要要使 x' 和 y' 都等于同一个数。很明显这个数越小越好，当这个数在区间 $[x,y]$ 时，代价是固定的 $x-y$. 由于这个代价能不花就不花，所以我们把 x' 和 y' 修改到到一个 k 使 $k\in [x,y]$ 就只需要花 $x-y$ 的代价。如果此时排在 y 前面的最大值 z 大于 y 就不符合单调性了，由于 z 不是堆顶、对单调性有影响，$z\in [x,y]$, 代价不变，为了不影响单调性将 x' 和 y' 都设为 z 就行了。弹入两个 x 的操作先不谈，此时我们多了两个 z 了，难道不应该把两个 z 弹进堆里面吗？实际上，这两个 z 的数量贡献都是假的，这里称为假值，因为维护单调性，前面的元素 $x'=y'=k$ 越小越好，一旦 z 也被后面新加的元素被迫修改，x' 和 y' 就不如设为剩下最大的值 $k\in [x,y]$, 代价一样而且由于 z 似掉了不会破坏单调性。如果所有 $k\in [x,y]$ 都没了，这时候 x' 和 y' 都变成靠得住的真值了，因为你再进行 +1 就会影响后面的元素，再 -1 又会花更多代价。所以这时候将 x' 和 y'（都等于 x) 弹入大根堆。当然这个操作可以简化，由于大根堆的特性只会弹最大的数，因此我们可以先在遍历时就把两个 x 的值弹进去，x' 和 y' 在可用的 k 存在时是不会被弹到堆顶的，相当于滚木，直到所有可用的 k 都没了，这两个值才会有用。

Code：

#include<bits/stdc++.h>
using namespace std;
priority_queue<int>q;
int n,k;
long long ans;
long long read(){
    long long x=0;int f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(long long x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read();
    while(n--){
        k=read(),q.push(k);
        if(q.top()>k)ans+=q.top()-k,q.pop(),q.push(k);
    }
    write(ans);
    return 0;
}

但是还有另一种做法。

2.整体二分
整体二分需要有符合单调性的询问，但是这个问题没有询问，也没有单调性怎么办？

诶，真的没有单调性吗？

单调性，就在你构造的序列当中！

我们二分的 mid 现在是指当前二分的值域，每次递归我们求出 mid 这个值域所在的位置。如图：

我们计算出对于某个 mid, 最优的位置使得在这个位置之前所有值域小于等于 mid 绝对比这个位置之前所有值域小于等于 mid+1 要好。计算出这个位置之后向这个位置两边递归。如何判断一个位置以前是否一定都小于等于 mid 更好？当一个位置 pos 满足 $\sum_{i=1}^{pos} \lvert a_{pos}-mid\rvert$ 最小即可，我们将最小值初始化为 $\sum_{i=1}^{N} \lvert a_{pos}-mid-1\rvert$. 请结合代码实现和刚才的讲述自主思考。每次递归只用把整个序列遍历一遍即可，时间复杂度 $O(N\log N)$.

注意到这是标准的题解做法，很迷惑，但是你抄板子不就行了吗？

题解做法其实就是统计区间内有多少个数小于等于 $mid$. 先给出题解做法的代码。

Code:

#include<bits/stdc++.h>
using namespace std;
priority_queue<int>q;
int n,k;
long long ans;
long long read(){
    long long x=0;int f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(long long x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read();
    while(n--){
        k=read(),q.push(k);
        if(q.top()>k)ans+=q.top()-k,q.pop(),q.push(k);
    }
    write(ans);
    return 0;
}

然后讲讲简单实现。其实很简单，设两个分割点，一个是目前的最优分割点，一个是其它分割点，根据题意模拟这个其它分割点在右边。这两个分割点形成一个区间，对于这个区间里小于等于 $mid$ 的值数量 $x$ 和 大于 $mid$ 的值的数量 $y$，由于整体二分强制把一个区间内的数划分进一个值域区间，所以最优分割点左边的所有数都必须小于等于 $mid$,右边都必须大于 $mid$.注意到左右两段的贡献没变，考虑中间段，如果选 $mid+1$，有 $y$ 个数加到 $mid+1$ 比加到 $mid$ 多一次操作，剩下 $x$ 个数加到 $mid+1$ 少一次操作，选 $mid$ 反之亦然。当 $x<y$ 时原来的分割点分割 $mid$ 更优，否则当前分割点更优。由于可以连续相同子段，因此被划分的中间区间里的数可以赖着不走，这样就不会对后面的操作产生影响。题解写的什么玩意。顺便把自己的最优解又加快了几十毫秒。去看看最优解记录吧。快麻了。

提交记录：https://www.luogu.com.cn/record/275260733

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
int n,a[500005];long long ans;
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(long long x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
void solve(int ql,int qr,int l,int r){
    if(l>r||ql>qr)return;
    if(l==r){for(int i=ql;i<=qr;++i)ans+=l>a[i]?l-a[i]:a[i]-l;return;}
    int mini,sum=0,maxn=0;
    mini=ql-1;
    for(int i=ql;i<=qr;++i){
        sum+=(a[i]<=mid)?1:-1;
        if(sum>maxn)maxn=sum,mini=i;
    }
    solve(ql,mini,l,mid),solve(mini+1,qr,mid+1,r);
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    solve(1,n,-1e9,1e9);
    write(ans);
    return 0;
}

双倍经验：P4331 [BalticOI 2004]Sequence(Day1)

这题不能用普通堆，因为要求输入具体方案。本题是一道可并堆好题，可惜蒟蒻我除了可并堆什么都不会。依旧整体二分。求严格上升只需要一开始把所有 $a_i$ 减去 i, 整体二分完再加回来就行了。ACGO 也有这题，但是没有整体二分解，我的代码一交上去不停地 WA, 检查发现 ACGO 改了数据，又交了一遍发现还是不行，原来此题要求输出一种方案，需要 Special Judge, 而 ACGO 这个 OJ 是【数据删除】

Code:

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
#define re register
#define il inline
typedef long long ll;
int n,a[1000005],b[1000005];ll ans;
il int read(){
    re int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
il void write(ll x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked((x%10)|48);
}
il void solve(int ql,int qr,ll l,ll r){
    if(l>=r||ql>qr)return;
    ll sum=0,minn,mini;
    for(re int i=ql;i<=qr;++i)sum+=abs(a[i]-mid-1);
    minn=sum,mini=ql-1;
    for(re int i=ql;i<=qr;++i){
        sum+=abs(a[i]-mid)-abs(a[i]-mid-1);
        if(sum<minn)minn=sum,mini=i;
    }
    for(re int i=ql;i<=qr;++i)b[i]=mid+(i>mini);
    solve(ql,mini,l,mid),solve(mini+1,qr,mid+1,r);
}
signed main(){
    n=read();
    for(re int i=1;i<=n;++i)a[i]=read()-i;
    solve(1,n,0,2e9);
    for(re int i=1;i<=n;++i)ans+=abs(a[i]-b[i]);
    write(ans),putchar_unlocked('\n');
    for(re int i=1;i<=n;++i)write(b[i]+i),putchar_unlocked('\n');
    return 0;
}

由于 ACGO 文章的字数限制，本文将分为上下两部分。下篇原计划和上篇一起出，不过内容过于复杂先咕咕咕一会。反正很快也会出的！

---

↑被腰斩的痕迹
↑宇髓天元的分割线