线段树分治

-1 前言

实际上这个东西和大部分其他诸如点分治，线段树二分之类，听起来很难很复杂，但是至少其内在的原理和模板题并算不上十分复杂。

然而我好像还是学了很长的时间。

我是菜鸡。

这次尝试换一种不同的风格来写。

0 前置芝士

• 线段树

• 分治

• （可选的）并查集

• （可选的）二分图

1 什么是线段树分治

线段树分治，顾名思义，就是把线段树和分治拼一块（不是）。

但是实际上这么说也有道理。

比较正经的一个回答是，我们想一个问题：线段树最擅长解决什么类型的问题？很显然是区间类问题。

那么假设这样一类问题：每个操作对一段区间内的状态有影响，并且需要询问一些较为复杂的判定或者计数问题。

这样的问题显然不好用普通的线段树和分治去解决，那么就需要我们今天的主角——线段树分治。

2 线段树分治的原理

（注：下文所有内容均以 P5787 二分图 /【模板】线段树分治 - 洛谷 为例。）

线段树分治，实际上就是在线段树上维护信息的基础上，再在线段树上dfs，分治处理询问。

比如我们拿到这道模板题，观察性质，首先发现 $k$ 的范围不大。

然后考虑一条边的贡献问题。一条边当且仅当出现，即第 $i$ 条边只在 $[l,r]$ 这个时间段内对于的答案有贡献。

综合以上两点，我们可以对于每个时刻考虑，考虑每个时刻都有哪些边有贡献，然后分别采用高效的方法判定二分图即可。

但是，注意到此方法暴力判断每一时刻边是否存在并且添加边的操作时间复杂度为 $O(m)$，总的仅仅加边的复杂度就高达 $O(mk)$ ，对于 $2\times10^5$ 的数据显然无法通过。

那么对于这样的数据，加上大量的区间操作，那么我们自然而然的应该想到——线段树。

因此，我们考虑对于时间建一颗线段树，将每条边插入其出现的时间区间。因此可以发现，线段树每个叶子节点 $[i,i]$ 维护的的就是 $i$ 时刻所有出现的边的编号。

因此，接下来的步骤就很自然了。 我们在线段树上 $dfs$，从根节点上遍历到每个叶子节点，用一个可撤销的影子冰碴子并查集来判定当前图是否为二分图，然后从判定完成一个节点图状态后撤销所有操作，接着计算下一个点。

依照以上思路可以通过此题，并且也是较简单线段树分治题目的大体思路。

3 实现细节

关于此题的代码实现，实际上有不少细节需要注意。

有一个傻子因为细节被卡了一上午，我不说是谁。

由于为了保证良好的时间复杂度，我们采用一种聪明的办法判定二分图，那也就是影子并查集。

而且由于我们要支持可撤销的操作，所以不能使用路径压缩，为了保证复杂度，我们使用按秩合并。

关于如何使用影子并查集判定二分图，可以自行上网查询教程。这里简述一下：利用影子并查集敌人和朋友的关系，每次添加一组边上的两个点为敌对关系。如果遍历到存在一组边两端上的点最后为朋友关系，那么此图不是二分图，反之则是。

最后就是各种初始化，并且注意相关数据范围。

很丑陋的部分示例代码如下：

int n,m,k;
vector<pair<int,int>> edge;
int fa[N*2],siz[N*2],ans[N*2];
stack<tuple<int,int,int>> st;
void dsu_init(){
    for(int i=1;i<=400010;++i){//注意务必看清此处初始化的数据范围
        fa[i]=i,siz[i]=1;
    }
}
int find(int x){if(x==fa[x])return x;return find(fa[x]);}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    if(siz[x]>siz[y])swap(x,y);
    st.push(make_tuple(x,y,siz[y]));//储存当前并查集信息，为了撤销
    fa[x]=y;siz[y]+=siz[x];
}
void tolst(int fn){//撤销到状态栈中只有fn个状态的状态
    while(st.size()>fn){
        auto tmp=st.top();
        st.pop();
        int u=get<0>(tmp);
        int v=get<1>(tmp);
        int w=get<2>(tmp);
        fa[u]=u;
        siz[v]=w;
    }
}
vector<int> seg[N*4];
void update(int u,int l,int r,int L,int R,int k){
    if(L<=l&&r<=R){
        seg[u].push_back(k);
        return;
    }elif(R<l||r<L) return;
    int mid=l+r>>1;
    update(lb,l,mid,L,R,k);
    update(rb,mid+1,r,L,R,k);
}
void dfs(int u,int l,int r){//线段树分治主体部分
    int zt=st.size();
    bool flag=1;
    for(auto &i:seg[u]){
        int u=edge[i].first,v=edge[i].second;
        if(find(u)==find(v)||find(u+N)==find(v+N)){
            flag=0;
            break;
        }
        merge(u,v+N);merge(v,u+N);
    }
    if(!flag){
        for(int i=l;i<=r;++i)ans[i]=0;
    }elif(l==r){
        ans[l]=1;
    }else{
        int mid=l+r>>1;
        dfs(lb,l,mid);
        dfs(rb,mid+1,r);
    }
    tolst(zt);
}//实际上很简单对吧

4 时间复杂度分析

对于加边操作，这也就是常规的线段树，复杂度 $O(m\text{log}n)$。

对于线段树分治计算答案的部分， 待补。

5 后记

“嘿，伙计，你说我们将去往何方？”

“去码头整点薯条。”

“不，伙计，你误会了，我指的是我们这一生的，终极的方向。或者说，我们这样的飞行，是为了什么？”

”为了，去码头整点薯条。“