0x47 复杂分治算法

· · 个人记录

分治算法的基本思路

分治算法的基本思路，即为将答案状态空间均等或不均等分为两部分，分别递归计算两部分的值，再通过某些方法将两部分的结果合并为一部分的答案。即：

而对于不同的情景，分治大体思路都是如此，只不过一方面子集划分方式可能不同，另一方面可能会涉及到一个序列对另一个序列产生的影响，需要在其中加入修改操作。

复杂分治思想主要分为三类：

  1. 对实体区间进行分治
  2. 对操作时间区间进行分治
  3. 对操作值域进行分治

一般如果有实体区间就按实体区间进行分治，否则如果有操作序列就按时间分治，如果答案单调则考虑对值域分治

因此诞生了以下几种主要的复杂分治思想：

离线分治算法

大部分问题都可以分为离线问题和在线问题两类：

其中离线问题一般使用离线算法解决，即不按照时间顺序处理操作；而在线问题一般用在线算法解决，即按照时间顺序处理操作。

一般情况下，离线问题解决难度低于在线问题，因此如果题目不强制在线，就可以将在线问题用离线分治转化为离线问题，并用离线算法解决。

（注意这里的“操作”并不一定指的是实际的query，也可以是问题转化得到的需要查询的信息）

离线分治主要有以下两种情况：

CDQ*分治（基于时间的分治算法）

基于时间，指的是在原操作序列上进行分治，分治过程中不改变操作的前后顺序或所在位置（下标）

由于操作（或广义的信息）的下标关系不会发生改变，CDQ分治很适合处理多维偏序问题

*CDQ来源于IOI2008金牌女选手陈丹琦，她最早在论文中将这一思想引进国内

多维偏序问题

如果每一个元素用一个元组 (a_i,b_i,\cdots) 表示，且定义了两个元组之间的偏序关系（即每一个对应维度上都定义了某种大小或其他比较关系），求满足这种偏序关系的元素对数，那么这就是一个多维偏序问题。

最常见的问题包括求逆序对数，它是一个二维偏序问题（即满足 i<j\& a_i>a_j 的元素对数）。这时候可以保持下标关系不变，用树状数组求满足第二维偏序的元素数量。

对于这种问题，一般先保持某一维偏序关系成立，然后用数据结构或算法求剩下几维偏序关系。

CDQ分治由于没有改变下标关系（或时间顺序），非常适合求包含一维下标偏序的多维偏序问题。

CDQ分治的过程

由于是分治，主要分为四个部分：

这四部分的顺序是不定的，且第三部分在没有修改的时候有可能不需要，一般情况下的顺序是1234或1324

下面以几道例题来具体讲解：

P3157 动态逆序对

在这道题当中，题意可转化为一个三维偏序问题，CDQ的解决过程即为：

  1. 按原序列顺序分成两部分，满足 i<j
  2. 两部分之间按删除时间t值排序，满足 t_i<t_j
  3. 用树状数组处理第三维 a_i>a_j

实现细节：只要记录每个元素原来的编号，就可以在独立的ans数组中记录答案。

这道题中分治递归过程是任意的，不过由于t值需要排序，可以同时进行按t为关键字的归并

P4093 序列

首先写出dp转移方程：f_i=\max\limits_{j\in [1,n),a_j\leq a_i}\{f_j\}+1

但是这个方程的条件中，a_j和 a_i 都有多个可能的变化情况（每次只有其中一个改变），不妨记录 ma_i 为i位置的数能变到的最大值，mi_i 为i位置的数能变到的最小值，转移条件就变为了：

\{i\to j|i<j\&ma_i\leq a_j\&a_i\leq mi_j\}

非常裸的三维偏序问题，可以用CDQ分治解决。

首先通过序列上分治，保证了第一维 i<j，然后分治的合并过程中，左边区间按照 ma_i 升序，右边区间按照 a_j 升序，然后用双指针归并方法跑一遍，第三维则用最值树状数组，对于左区间在 a_i 位置上添加 f_i，对于右区间直接计算 mi_j 的前缀最大值，转移给 f_j 即可

另外，由于右边的f依赖于左边的f，应先递归计算左边的f，然后计算左边对右边的贡献，最后再递归右边计算。这是比较符合标准的CDQ分治思路的

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100010
int n,m,maxn,ans,f[N];
class data{//数据元组
    public:
    int id,v,ma,mi;
}a[N];
bool cmpv(data x,data y){
    return x.v<y.v;
}bool cmpid(data x,data y){
    return x.id<y.id;
}bool cmpma(data x,data y){
    return x.ma<y.ma;
}
class listree{//最值树状数组
    public:
    #define lb(x) (x&-x);
    int c[N];
    void add(int x,int v){//修改最值
        while(x<=maxn){
            c[x]=std::max(v,c[x]);
            x+=lb(x);
        }return;
    }void clear(int x){//清零
        while(x<=maxn){
            c[x]=0;
            x+=lb(x);
        }return;
    }int max(int x){//前缀最值
        int ans=0;
        while(x){
            ans=std::max(ans,c[x]);
            x-=lb(x);
        }return ans;
    }
}lt;
void solve(int l,int r){//CDQ
    if(l==r)return;
    int mid=(l+r)>>1;
    solve(l,mid);//先处理左区间
   //下面计算左区间对右区间的贡献
    std::sort(a+mid+1,a+r+1,cmpv);//右边按原值排序
    std::sort(a+l,a+mid+1,cmpma);//左边按最大值排序
    int i,j;
    for(i=l,j=mid+1;i<=mid&&j<=r;){//归并法走双指针
        if(a[i].ma<=a[j].v)lt.add(a[i].v,f[a[i].id]),i++;//当前i满足条件，往树状数组里添加，走i
        else f[a[j].id]=std::max(f[a[j].id],lt.max(a[j].mi)+1),j++;//当前i不满足条件，计算当前j的答案，走j
    }while(i<=mid)lt.add(a[i].v,f[a[i].id]),i++;//此行可不要
    while(j<=r)f[a[j].id]=std::max(f[a[j].id],lt.max(a[j].mi)+1),j++;//计算剩下的j
    for(int i=l;i<=mid;i++)lt.clear(a[i].v);//撤销树状数组操作
    std::sort(a+l,a+r+1,cmpid);//按下标恢复序列顺序
    solve(mid+1,r);
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].v);
        a[i].id=i,a[i].ma=a[i].mi=a[i].v;
        maxn=std::max(maxn,a[i].v);
        f[i]=1;//开始答案都为1
    }for(int i=1;i<=m;i++){
        int p,v;
        scanf("%d%d",&p,&v);
        a[p].ma=std::max(a[p].ma,v);
        a[p].mi=std::min(a[p].mi,v);
    }solve(1,n);
    for(int i=1;i<=n;i++)ans=std::max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

整体二分（基于值域的分治算法）

分别二分答案

二分答案的本质，就是按照答案值域判断当前询问答案所在区间，并进一步确定最优位置

例如，要求一个序列的第k小数，就可以估计一个mid，统计小于mid的数的数量cnt(都是在值域上二分)：

再根据二分的思路，并暴力求解比mid小的数的数量，就可以在 O(n\log a) （a为值域）的时间内求出一次询问的答案。

但是我们现在如果有q次询问，那么正常分别二分答案就会导致复杂度达到 O(nq\log a) 水平，显然不能接受。

整体二分答案

我们考虑一下，能否让所有询问共用同一个数据结构或同一个计算过程的信息，使得最终能够均摊数据结构的构建复杂度或计算过程复杂度？

不妨把所有询问放到一块进行二分答案，判断的时候根据mid位置的判断结果把每个询问分到两个答案值域区间内继续二分，如果最后值域二分到了唯一确定的值，那么就说明答案在这一区间内的询问的答案就是这个值。

发现这是一个分治的结构，因此有如下过程：

这样分治递归下去，就相当于将每个询问的答案一块二分答案，最后同时得到所有询问的答案。

如果判断部分的复杂度为 O(n\log n)，根据 T(n)=2T(n/2)+O(n\log n)，可得总的分治复杂度是加上了一个log，即 O(n\log^2 n)

第k小值

给定一个初始序列，有多个询问 l_i,r_i,k_i，询问序列中 [l_i,r_i] 区间的第 k_i 小值

这个问题非常适合用整体二分解决（虽然正解是主席树，就是这道题）

对每个询问考虑二分答案，我们可以先二分一个mid值，然后考虑在区间l到r中比mid小的数的个数cnt，然后确定这个询问的答案和mid的关系

发现查找的建立是一个瓶颈，因此我们希望可以让一些询问共享一个数据结构，能够同时查出不同区间中的比mid小的数的个数。

首先对于每个序列元素，我们用 (val,id) 这样的二元组表示，分别存储值和序列中的位置；对于每个询问，用 (l,r,k) 这样的三元组表示，这样后面集合分类的时候会比较好处理。

使用整体二分，solve(l,r,A,X) 表示 A 集合中的询问答案都在 [l,r] 之中，且序列中小于，下面需要做的是判断 [l_i,r_i] 中小于mid的数的数量。

现在值域上的限制已经用分治处理了，接下来需要序列上的限制，因此对序列建立树状数组，记录小于等于mid的数的位置，对于每个询问，计算它所询问区间内小于等于mid的数有cnt个：

接着判断每个元素的归属：

注意最后序列树状数组需要回退到递归刚开始的状态，可以把当前A集合中的元素跑一遍，在相应位置加上-1即可。

最后继续递归 solve(l,mid,LQ,LA),solve(mid+1,r,RQ,RA)

边界：如果 l=r，那么当前 Q 集合中所有询问的答案都是 l

下面是过程的模拟图：

另外，为了节省空间，可以直接在原数据序列和查询序列上进行交换操作（类似归并），然后用两侧指针标记处理区间：

时间复杂度分析：如果判断部分的复杂度为 $O(n\log n)$，根据 $T(n)=2T(n/2)+O(n\log n)$，可得总的分治复杂度是加上了一个log，即 $O(n\log^2 n)

P1527

二维第k小值：整体二分+二维树状数组

首先由于是离线第k小值，还没有修改操作，可以直接用整体二分做。考虑到需要在矩阵中查询，因此用二维树状数组做。

二维树状数组，顾名思义，就是在两个维度上树状数组套树状数组，我们可以用列树状数组在内部，行树状数组在外部，在x行y列的某个位置修改时，就按x跳lowbit，跳到的列树状数组的第y位置进行修改即可。

查询的时候就跳x，然后查跳到的树状数组的第y位置的前缀和即可。

显然在列上的跳法是正确的，而行上的跳法如果把每个列树状数组都只当做一个数的话，相当于就是一个普通的树状数组，因此也是正确的。（x列树状数组的y位置保存了从lowbit(x)到x列的所有y位置的前缀和）

剩下就是裸的第k小数模板了：

#include<iostream>
#include<cstdio>
#define N 510
#define Q 60010
#define lb(x) (x&-x)
int n,que,ans[Q],maxx;
class listree{//列树状数组
    public:
    int c[N];
    void add(int x,int v){
        while(x<=n){
            c[x]+=v;
            x+=lb(x);
        }return;
    }int sum(int x){
        int ans=0;
        while(x){
            ans+=c[x];
            x-=lb(x);
        }return ans;
    }
};
class query{//询问元组
    public:
    int x1,y1,x2,y2,k,id;
}q[Q];
class data{//数据元组
    public:
    int x,y,v;
}a[N*N];
class listreedb{//行树状数组
    public:
    listree c[N];//树套树
    void add(int x,int y,int v){
        while(x<=n){
            c[x].add(y,v);
            x+=lb(x);
        }return;
    }int sum(int x,int y){
        int ans=0;
        while(x){
            ans+=c[x].sum(y);
            x-=lb(x);
        }return ans;
    }int sum(query a){//计算a区间的和
        return sum(a.x2,a.y2)-sum(a.x1-1,a.y2)-sum(a.x2,a.y1-1)+sum(a.x1-1,a.y1-1);
    }
}lt;
void swap(query &a,query &b){//交换询问
    query tmp=a;
    a=b,b=tmp;
}void swap(data &a,data &b){//交换数据
    data tmp=a;
    a=b,b=tmp;
}void solve(int l,int r,int la,int ra,int lq,int rq){//用指针标记询问和数据区间，整体二分
    if(lq>rq||la>ra)return;//没有询问或没有数据在值域中，跳出
    if(l==r){//确定答案
        for(int i=lq;i<=rq;i++)ans[q[i].id]=l;//记录
        return;
    }int mid=(l+r)>>1,mq=rq,ma=ra;//三个中点
    for(int i=la;i<=ma;){//给数据分类为小于等于mid和大于mid两组
        if(a[i].v<=mid)i++;
        else swap(a[i],a[ma--]);
    }for(int i=la;i<=ma;i++)lt.add(a[i].x,a[i].y,1);//只加左边组
    for(int i=lq;i<=mq;){//给询问分类
        int s=lt.sum(q[i]);
        if(s>=q[i].k)i++;
        else q[i].k-=s,swap(q[i],q[mq--]);
    }for(int i=la;i<=ma;i++)lt.add(a[i].x,a[i].y,-1);//树状数组回退
    solve(l,mid,la,ma,lq,mq),solve(mid+1,r,ma+1,ra,mq+1,rq);//二分
    return;
}
int main(){
    scanf("%d%d",&n,&que);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[(i-1)*n+j].v);
            a[(i-1)*n+j].x=i,a[(i-1)*n+j].y=j;
            maxx=std::max(maxx,a[(i-1)*n+j].v);
        }
    }for(int i=1;i<=que;i++){
        scanf("%d%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2,&q[i].k);
        q[i].id=i;
    }solve(1,maxx,1,n*n,1,que);
    for(int i=1;i<=que;i++)printf("%d\n",ans[i]);
    return 0;
}

P2617 Dynamic Rankings

这道题有了修改，感觉不是很好做。

预处理

可以考虑把初始化的一列n个数也变成修改，那么就可以将Q和A两个序列合并。

发现一次修改不仅会添加一个新数，也会去掉原来的旧数，因此一个修改可以拆成两个：在pos位置去掉原来那个值，在pos位置加上新的值。

这样就用至多 2m+n 个操作表示了C和Q序列，称之为query序列。

query序列可以用元组 (id,lp,rp,k,pos,v,ans,s) 表示：

然后设函数 \text{solve}(lx,rx,lq,rq) 表示目前查询的值域为 [lx,rx] 且query序列为 q[lq...rq] 这一段，现在要对query中所有查询操作查询其在 [lp_i,rp_i] 序列区间内的第k小值

大致思路

  1. 在序列树状数组中记录每一时刻 \leq mid 的数在什么位置出现了
  2. 查询时回答当前时刻 [lp_i,rp_i] 区间内有多少个数
  3. 按照查询结果将询问分为答案小于等于mid和答案大于mid两组
  4. 将修改操作分类为值小于等于mid和值大于mid两组
  5. 回退掉树状数组，继续递归这两组

实际实现过程中，3和4操作是同时进行的，因为我们需要保证query序列的有序性

程序实现

下面来具体讲一下操作方式，如果遇到了修改操作：

（注意树状数组是建在序列上的，query的修改值v只用于分辨是否在值域内）

如果遇到了查询操作：

接下来需要分类：

首先找出所有满足以下条件的操作，按序放在query段的前面：

再将剩下操作按序放在query段的后面（注意这里k要减去s）

记录一下两部分分界点 midq

撤销树状数组（注意只有v小于等于mid的操作）

递归 \text{solve}(lx,mid,lq,midq),\text{solve}(mid+1,rx,midq+1,rq)

如果遇到 lq>rq 则直接回溯，如果遇到 lx=rx ，当前query中的查询答案都设为 lx

至此整个算法就结束了

正确性说明

其他问题都好解决，而且事实上已经在前面讲静态区间k小值算法的时候说过了，现在主要来解决：为什么可以把修改值大于mid的放在一边不看，或者把修改值小于等于mid的放在另一边不看？

实际上根据 solve() 的定义可以看出，我们已经使得答案只是在当前值域内的数的第k小值了（通过k减去s来实现），那么显然不在当前值域内的添加和删除是不可能也绝不可以影响当前区间的查询情况的，因此可以放心地置之不理了。

代码

#include<bits/stdc++.h>
#define N 100010
std::map<int,int> mp,ump;
int n,m,tot,a[3*N],init[N];
class query{
    public:
    int id,l,r,k,pos,v,ans,s;
    bool operator <(query a)const{
        return id<a.id;
    }bool ischange(){
        return id<1;
    }
}q[3*N],tmp[3*N];
class listree{
    public:
    #define lb(x) (x&-x)
    int c[3*N];
    void add(int x,int v){
        while(x<=n){
            c[x]+=v;
            x+=lb(x);
        }return;
    }int sum(int x){
        int s=0;
        while(x){
            s+=c[x];
            x-=lb(x);
        }return s;
    }
}lt;
void solve(int lx,int rx,int lq,int rq){
    if(lq>rq)return;
    if(lx==rx){
        for(int i=lq;i<=rq;i++)q[i].ans=lx;
        return;
    }int mid=(lx+rx)>>1,cnt=lq-1,midq;
    for(int i=lq;i<=rq;i++){
        if(!q[i].ischange()){
            q[i].s=lt.sum(q[i].r)-lt.sum(q[i].l-1);
            if(q[i].k<=q[i].s)tmp[++cnt]=q[i];
        }else{
            if(q[i].id==-1&&q[i].v<=mid)lt.add(q[i].pos,-1);
            else if(q[i].v<=mid)lt.add(q[i].pos,1);
            if(q[i].v<=mid)tmp[++cnt]=q[i];
        }
    }midq=cnt;
    for(int i=lq;i<=rq;i++){
        if(!q[i].ischange()&&q[i].k>q[i].s)q[i].k-=q[i].s,tmp[++cnt]=q[i];
        else if(q[i].ischange()&&q[i].v>mid)tmp[++cnt]=q[i];
    }for(int i=lq;i<=rq;i++){
        if(q[i].id==-1&&q[i].v<=mid)lt.add(q[i].pos,1);
        else if(q[i].id==0&&q[i].v<=mid)lt.add(q[i].pos,-1);
        q[i]=tmp[i];
    }solve(lx,mid,lq,midq),solve(mid+1,rx,midq+1,rq);
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    tot=n;
    for(int i=1;i<=n;i++){
        q[i].id=0,q[i].pos=i;
        scanf("%d",&q[i].v);
        init[i]=a[i]=q[i].v;
    }for(int i=1;i<=m;i++){
        ++tot;
        q[tot].id=tot;
        char opt[10];
        scanf("%s",opt);
        if(opt[0]=='C'){
            q[tot].id=-1,scanf("%d%d",&q[tot].pos,&q[tot+1].v);
            q[tot].v=init[q[tot+1].pos=q[tot].pos];
            q[++tot].id=0,a[tot]=q[tot].v,init[q[tot].pos]=q[tot].v;
        }else scanf("%d%d%d",&q[tot].l,&q[tot].r,&q[tot].k);
    }std::sort(a+1,a+tot+1);
    //for(int i=1;i<=tot;i++)printf("id:%d pos:%d\n",q[i].id,q[i].pos);
    int tt=0;
    for(int i=1;i<=tot;i++)if(a[i]!=a[i-1])mp[a[i]]=++tt,ump[tt]=a[i];
    for(int i=1;i<=tot;i++)q[i].v=mp[q[i].v];
    solve(0,tt,1,tot);
    std::sort(q+1,q+tot+1);
    for(int i=1;i<=tot;i++)if(q[i].id>0)printf("%d\n",ump[q[i].ans]);
    return 0;
}

P3527

首先处理掉环的问题，把 l>r 的操作拆分为两部分即可。

然后考虑对达到目标的时间（答案）进行二分，如果只二分一个国家的情况，方法显然是：对操作序列二分，每次将 [l,mid] 区域内的操作执行，由于是区间修改单点查询，可以用树状数组加差分实现，然后直接计算该国家在mid处是否满足目标，二分即可。

对于整体二分的情况：可以枚举答案在当前范围 [l,r] 里的国家，枚举它们拥有的空间站，就可以判断执行到mid以后能不能满足目标，能满足的国家放在左边，不能满足的放右边。

注意，这里我们希望这棵树状数组可以在接下来的递归当中使用，因此我们先解决右区间的情况 solve(mid+1,r,RQ)，然后操作回退到l处，再解决左区间的情况 solve(l,mid,LQ)

另外为了判断无解的情况，主函数调用solve时处理的答案区间应为 [1,q+1]，q为操作数量

复杂度分析：

代码：

#include<iostream>
#include<cstdio>
#include<vector>
#define N 300010
#define ll long long
typedef std::vector<int> vec;
class operation{//操作元组
    public:
    int l1,r1,l2,r2;
    ll val;
    operation(){
        l1=r1=l2=r2=0;
    }
}q[N];
int n,m,k,ans[N];//ans记录每个国家的答案
class treelist{//树状数组
    public:
    #define lb(x) (x&-x)
    ll c[N];
    void add(int x,ll val){
        while(x<=m){
            c[x]+=val;
            x+=lb(x);
        }return;
    }ll sum(int x){
        ll ans=0;
        while(x){
            ans+=c[x];
            x-=lb(x);
        }return ans;
    }void plus(operation a,ll opt){//简化操作函数
        if(a.l1)add(a.l1,a.val*opt),add(a.r1+1,-a.val*opt);
        if(a.l2)add(a.l2,a.val*opt),add(a.r2+1,-a.val*opt);
        return;
    }
}st;
vec tmp,na[N],alist;//国家（询问）集合，alist是初始国家集合
ll p[N];
void swap(vec &a,vec &b){
    tmp=a,a=b,b=tmp;
    return;
}
void solve(int l,int r,vec list){
    if(l==r){//边界，判断是否无解
        for(int i=0;i<list.size();i++)ans[list[i]]=l>k?-1:l;
        return;
    }int mid=(l+r)>>1;
    for(int i=l;i<=mid;i++)st.plus(q[i],1);//在树状数组中添加操作
    vec list1,list2;//两边的询问序列
    for(int i=0;i<list.size();i++){//对于所有在当前询问序列中的国家都看一遍
        int x=list[i];
        ll sum=0;
        for(int j=0;j<na[x].size();j++){//看一遍当前国家的所有点
            sum+=st.sum(na[x][j]);
            if(sum>=p[x]){list1.push_back(x);break;}//数据有可能爆longlong，所以要特判跳出，这时候mid已经可以使这个国家达成目标，因此放到左区间
        }if(sum<p[x]) list2.push_back(x);//如果不能达成目标，放到右区间
    }solve(mid+1,r,list2);//先计算右区间
    for(int i=mid;i>=l;i--)st.plus(q[i],-1);//撤销树状数组的操作。
    solve(l,mid,list1);//计算左区间
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a;
        scanf("%d",&a);
        na[a].push_back(i);
    }for(int i=1;i<=n;i++){
        scanf("%lld",&p[i]);
        alist.push_back(i);
    }scanf("%d",&k);
    for(int i=1;i<=k;i++){
        int l,r;
        scanf("%d%d%lld",&l,&r,&q[i].val);
        if(l<=r)q[i].l1=l,q[i].r1=r;
        else q[i].l1=l,q[i].r1=m,q[i].l2=1,q[i].r2=r;
    }solve(0,k+1,alist);//注意用k+1判断无解情况
    for(int i=1;i<=n;i++){
        if(ans[i]==-1)printf("NIE\n");
        else printf("%d\n",ans[i]);
    }return 0;
}

在这道题当中，二分的答案就是操作序列本身，因此就不需要再用一个集合表示符合要求的操作序列了。

其它分治思想

启发式分治

核心思想：每次合并两个大小不同的集合，合并复杂度保证为较小集合的复杂度

线段树分治

线段树分治有两种形式：

利用线段树进行区间分治

纯线段树算法支持以下操作：

  1. 单点或区间修改
  2. 单点或区间查询

如果某个操作信息在不同相邻区间之间可以合并，那么就可以用线段树维护这个区间，并在回溯的时候合并更新上面的节点

（实际上就是一个线段树，没啥特别的，只不过节点里面维护的信息变复杂了）

P4435 Garaža

考虑分治的思路，两边分别统计，最后计算跨区间的满足条件的数对数量。这可以记录左边区间的后缀gcd，右边区间的前缀gcd，然后由于单调用双指针法计算即可。

又因为gcd每改变一次一定都至少为原来一半，所以前后缀gcd不同的段个数只有log级别。

这个分治结构可以用线段树来维护。

用线段树对序列进行操作：修改的时候单点修改。

void change(int x,int pos,int val){
        if(a[x].r<pos||a[x].l>pos)return;
        if(a[x].l==a[x].r&&a[x].l==pos){
            a[x].bk.clear(),a[x].fr.clear();
            a[x].bk.push_back((glist){pos,val});
            a[x].bk.push_back((glist){pos-1,1});
            a[x].fr.push_back((glist){pos,val});
            a[x].fr.push_back((glist){pos+1,1});
            if(val>1)a[x].sum=1;
            else a[x].sum=0;
            return;
        }change(ls(x),pos,val),change(rs(x),pos,val);
        a[x]=merge(a[ls(x)],a[rs(x)]);
        return;
    }

两个子节点合并到父节点的时候，先加上两边的统计值，再用双指针法算跨区间的值，最后用两边的前后缀gcd更新当前大区间gcd

node merge(node x,node y){
        node ans;
        vec &lfv=x.fr,&lbv=x.bk,&rfv=y.fr,&rbv=y.bk,&fv=ans.fr,&bv=ans.bk;
        int G=0,mid=x.r;
        ll sum=x.sum+y.sum;
        for(int lp=lbv.size()-2,rp=0;lp>=0&&rp<(int)rfv.size();lp--){//统计答案
            while(gcd(lbv[lp].v,rfv[rp].v)>1)rp++;
            sum+=(ll)(lbv[lp].p-lbv[lp+1].p)*(rfv[rp].p-mid-1);
        }for(int i=0;i<(int)lfv.size()-1;i++){//更新前缀
            int gg=gcd(G,lfv[i].v);
            if(gg!=G)fv.push_back((glist){lfv[i].p,G=gg});
        }for(int i=0;i<(int)rfv.size()-1;i++){//更新前缀
            int gg=gcd(G,rfv[i].v);
            if(gg!=G)fv.push_back((glist){rfv[i].p,G=gg});
        }G=0;
        for(int i=0;i<(int)rbv.size()-1;i++){//更新后缀
            int gg=gcd(G,rbv[i].v);
            if(gg!=G)bv.push_back((glist){rbv[i].p,G=gg});
        }for(int i=0;i<(int)lbv.size()-1;i++){//更新后缀
            int gg=gcd(G,lbv[i].v);
            if(gg!=G)bv.push_back((glist){lbv[i].p,G=gg});
        }bv.push_back((glist){x.l-1,1}),fv.push_back((glist){y.r+1,1});
        ans.sum=sum,ans.l=x.l,ans.r=y.r;
        return ans;
    }

查询的时候，任何一个查询区间都会被分成log段，然后用一般的查询函数，最后合并区间即可。

    node calc(int x,int li,int ri){
        if(a[x].r<li||a[x].l>ri)return node(0);
        if(li<=a[x].l&&a[x].r<=ri)return a[x];
        node L=calc(ls(x),li,ri),R=calc(rs(x),li,ri);
        if(L.l==0)return R;//左区间为空
        if(R.l==0)return L;//右区间为空
        else return merge(L,R);//都不为空
    }

利用线段树对时间分治

除了直接对序列分治，分治思想中还有对时间进行分治，因此线段树分治也可以解决对时间分治的问题。

如果一个操作序列中既包括添加、插入操作，又包括删除撤销操作，而所用的数据结构不支持随机访问删除，只支持撤销上一步操作，那么这时候很适合用线段树时间分治

具体方法就是对时间构造一棵线段树，然后按每个操作影响的时间区间将该操作加到线段树上（即在有关节点的vector里面加上该操作），这段影响区间最多会被分成log份，因此，在线段树节点上最多只会加入qlogn个操作，全部都存在每个节点的vector中。

void addopt(int x,int li,int ri,operation o){
    if(a[x].r<li||a[x].l>ri)return;
    if(li<=a[x].l&&a[x].r<=ri)a[x].opt.push_back(o);//加入该节点的操作序列中
    else addopt(ls(x),li,ri,o),addopt(rs(x),li,ri,o);
    return;
}

对于询问，一般是在某些点，我们可以在所有操作都添加完成后，遍历整棵线段树。从根走到某个叶子的过程中，经过节点储存的操作都会对这个叶子结点产生影响，因此都进行计算，最后到达叶子之后进行判断即可（当然有时候可以提前判断不可行或可行，可以直接从中间节点跳出）

因此我们进入一个节点后，先处理所有这个节点的操作，然后递归，最后回溯时还原现场（我们所用的数据结构可以支持撤销上一步操作）。这里线段树分治不需要定点删除操作，它可以使每次数据结构只需撤销上一次操作，这也是其优势所在。

void solve(int x){//遍历整棵线段树
    bool flag=true;
    for(int i=0;i<a[x].opt.size();i++){
        //数据结构操作
    }if(flag){//可行
        if(a[x].l==a[x].r)ans[a[x].l]=1;//走到单点，标注可行
        else solve(ls(x)),solve(rs(x));//继续递归
    }for(int i=0;i<a[x].opt.size();i++)//数据结构撤销上一步操作
    return;
}

若操作数量为q，数据结构复杂度为 T(n)，则总复杂度为 O(qT(n)\log q )

P5787 二分图

首先考虑一下怎么判断二分图，最简单的方法是用扩展域并查集，如果两点x,y连边，那么xA和yB连边，xB和yA连边，连上这条边就变为不是二分图，当且仅当xA和yA在一个集合中

证明：

充分性显然，如果xA和yA在一个集合中，说明x和y应该分到一个点集，但是现在加上这一条边，同一点集内部的点也互相连上了边，显然不能构成二分图

必要性：如果有x，y和z三个点，扩展域后变成xA，xB，yA，yB，zA，zB六个点：

假设x和y连一条边会导致zA和zB相连，且xA和yA不在一组，不妨设xA和zA在一组，yB和zB在一组，这时候可知xB和zB也在一组，yA和zA也在一组，这样xA和yA就一定在一组，假设不成立，说明不会出现这样的情况。xA和yA在一组可以处理所有不是二分图的情况。

由于并查集采用按秩合并以后可以支持撤销一次操作的情况，因此我们可以用线段树时间分治来解决这个带删除操作的问题。

主要过就是将每个操作添加到线段树l到r区间上，然后全部添加完成以后进行遍历，遍历的时候用上面扩展域并查集的方法进行修改并判断是否为二分图即可。

代码：

#include<iostream>
#include<cstdio>
#include<vector>
#define N 200010
int n,m,ans[N],k;
class dsu{
    public:
    int f[N],h[N],top;
    class opt{
        public:
        int x,hy;
    }st[N];
    void newdsu(int n){
        for(int i=1;i<=n;i++)f[i]=i,h[i]=1;
        return;
    }int find(int x){
        if(f[x]==x)return x;
        return find(f[x]);
    }void merge(int x,int y){
        int fx=find(x),fy=find(y);
        if(h[fx]<h[fy])f[fx]=fy,st[++top]=(opt){fx,h[fy]};
        else if(h[fx]==h[fy])f[fx]=fy,st[++top]=(opt){fx,h[fy]},h[fy]++;
        else f[fy]=fx,st[++top]=(opt){fy,h[fx]};
        return;
    }void delopt(){
        h[f[st[top].x]]=st[top].hy,f[st[top].x]=st[top].x;
        top--;
        return;
    }
}d;
class operation{
    public:
    int x,y;
};
class segtreeDAC{
    public:
    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)
    class node{
        public:
        int l,r;
        std::vector<operation> opt;
    }a[2*N];
    void build(int x,int li,int ri){
        a[x].l=li,a[x].r=ri;
        if(li==ri)return;
        int mid=(li+ri)>>1;
        build(ls(x),li,mid),build(rs(x),mid+1,ri);
        return;
    }void addopt(int x,int li,int ri,operation o){//添加一条区间操作
        if(a[x].r<li||a[x].l>ri)return;
        if(li<=a[x].l&&a[x].r<=ri)a[x].opt.push_back(o);
        else addopt(ls(x),li,ri,o),addopt(rs(x),li,ri,o);
        return;
    }void solve(int x){//遍历线段树统计每个时刻的答案
        bool flag=true;
        for(int i=0;i<a[x].opt.size();i++){
            if(d.find(a[x].opt[i].x)==d.find(a[x].opt[i].y)){
                flag=false;
                for(int j=a[x].l;j<=a[x].r;j++)ans[j]=0;
            }d.merge(a[x].opt[i].x,a[x].opt[i].y+n);
            d.merge(a[x].opt[i].y,a[x].opt[i].x+n);
        }if(flag){
            if(a[x].l==a[x].r)ans[a[x].l]=1;
            else solve(ls(x)),solve(rs(x));
        }for(int i=0;i<a[x].opt.size();i++)d.delopt(),d.delopt();
        return;
    }
}st;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    d.newdsu(2*n);
    st.build(1,1,k);
    for(int i=1;i<=m;i++){
        int l,r,x,y;
        scanf("%d%d%d%d",&x,&y,&l,&r);
        st.addopt(1,l+1,r,(operation){x,y});
    }st.solve(1);
    for(int i=1;i<=k;i++)printf("%s\n",ans[i]?"Yes":"No");
    return 0;
}

P3733 八纵八横

首先有以下定理：一个无向图里面任意从1经过一些边到1的路径的异或值，可以用从1沿生成树边到u，再从u沿非生成树边到v，再从v沿生成树边到1的路径异或得到（具体证明及感性理解）

因此这个问题显然需要用线性基来处理，由于初始图连通，因此用dfs找一棵生成树，将初始的异或值扔进线性基，但线性基不支持删除操作只支持撤销，因此考虑使用线段树时间分治。

对于添加、删除操作，直接记录为这个边影响的区间即可，对于修改操作，先将原来的边记录一次删除，然后将原来的边修改即可。

最后遍历一遍线段树，在每个节点修改线性基，走到叶子节点更新那个位置的答案，回溯的时候撤销操作即可。

注意需要使用bitset，复杂度为 O(\frac{qL^2\log q}{w} )（线性基复杂度为 O(\frac{L^2}{w})）

#include<iostream>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<vector>
#define N 2050
#define uint unsigned int
typedef std::bitset<N> bit;
typedef std::string str;
int n,m,que,addt[N],cnt,len=1010;
bool vis[N];
bit dis[N],ans[N];
char s[N],opt[10];
str S;
class operation{
    public:
    int x,y;
    bit w;
}q[N];
class linearbase{
    public:
    int top,st[N];
    bit a[N];
    void add(std::bitset<N> val){
        for(int i=len-1;i>=0;i--){
            if(val[i]){
                if(a[i].count()==0){a[i]=val,st[++top]=i;return;}
                else val=val^a[i];
            }
        }st[++top]=-1;
        return;
    }void delopt(){
        if(st[top]!=-1)a[st[top]].reset();
        top--;
        return;
    }bit max(){
        bit ans(0);
        for(int i=len-1;i>=0;i--)if(ans[i]==0)ans^=a[i];
        return ans;
    }
}b;
class segtreeDAC{
    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)
    public:
    class node{
        public:
        int l,r;
        std::vector<operation> opt;
    }a[4*N];
    void build(int x,int li,int ri){
        a[x].l=li,a[x].r=ri;
        if(li>=ri)return;
        int mid=(li+ri)>>1;
        build(ls(x),li,mid),build(rs(x),mid+1,ri);
        return;
    }void addopt(int x,int li,int ri,operation o){
        if(a[x].r<li||a[x].l>ri)return;
        if(li<=a[x].l&&a[x].r<=ri)a[x].opt.push_back(o);
        else addopt(ls(x),li,ri,o),addopt(rs(x),li,ri,o);
        return;
    }void solve(int x){
        for(uint i=0;i<a[x].opt.size();i++)
            b.add(dis[a[x].opt[i].x]^a[x].opt[i].w^dis[a[x].opt[i].y]);
        if(a[x].l==a[x].r)ans[a[x].l]=b.max();
        else solve(ls(x)),solve(rs(x));
        for(uint i=0;i<a[x].opt.size();i++)b.delopt();
        return;
    }
}st;
int tot,hd[N],to[2*N],nxt[2*N];
bit val[2*N];
void newedge(int u,int v,bit w){
    nxt[++tot]=hd[u];
    to[tot]=v,val[tot]=w;
    hd[u]=tot;
    return;
}void dfs(int x){
    vis[x]=1;
    for(int i=hd[x];i;i=nxt[i]){
        int nex=to[i];
        if(!vis[nex]){
            dis[nex]=dis[x]^val[i];
            dfs(nex);
        }b.add(dis[nex]^val[i]^dis[x]);
    }return;
}
int main(){
    scanf("%d%d%d",&n,&m,&que);
    st.build(1,1,que);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d%s",&u,&v,s);
        S=s;
        newedge(u,v,bit(S)),newedge(v,u,bit(S));
    }dfs(1);
    for(int i=1;i<=que;i++){
        int u,v,k;
        scanf("%s",opt);
        if(opt[0]=='A'){
            scanf("%d%d%s",&u,&v,s);
            S=s;
            q[++cnt]=(operation){u,v,bit(S)},addt[cnt]=i;
        }else{
            scanf("%d",&k);
            st.addopt(1,addt[k],i-1,q[k]);
            if(opt[1]=='h'){
                scanf("%s",s);
                S=s;
                q[k].w=bit(S),addt[k]=i;
            }else addt[k]=-1;
        }
    }for(int i=1;i<=cnt;i++)if(addt[i]!=-1)st.addopt(1,addt[i],que,q[i]);
    ans[0]=b.max();
    st.solve(1);
    for(int i=0;i<=que;i++){
        bool flag=false;
        for(int j=len-1;j>=0;j--){
            if(ans[i][j]==1)flag=true;
            if(flag)printf("%d",(int)ans[i][j]);
        }if(!flag)printf("0");
        printf("\n");
    }return 0;
}

树上分治

请看 0x45 节