线段树分治的一系列（？）的题的讲解

 

于是，我发现我不会线段树分治。

P5787 模板题

题目描述：

有一个 个节点的图。在 时间点内有 条边会出现后消失。

要求出 每一时间段内这个图是否是二分图。

---

首先，考虑暴力怎么写。

暴力的程序非常好想。只要在每一个时间段内，diā出所有在这个时间段里面存在的边。然后连边。然后扩展域并查集判断是否为二分图。Over.

何为扩展域并查集判断是否为二分图？

二分图里面有一堆点。我们把每一个点 拆成两个点：原点和反点。他们的编号分别为 和 。

二分图里面有一堆边。如果点 和点 存在一条边，那么就在并查集里把 和 按秩合并。再把 和 合并。

那么如何判断什么时候不是二分图？只要在连边前判断 和 （都是原点）是否在同一连通块里即可。如果在，那么就不是一个二分图。

于是时间复杂度 。你过不了此题！

考虑优化。

---

怎么优化呢？我们可以把每一个时间段都拍到线段树上。就比如说，一条连接了点 的边在时间段 出现，那么就在线段树的 区间插入一条边 。

简要代码：

 void insert(int x, int ql, int qr, pii edge){
    int l = tr[x].l, r = tr[x].r;
    if(ql<=l&&r<=qr){
        tr[x].val.push_back(edge);
        return ;
    }
    int mid = l+r>>1;
    if(ql<=mid) insert(x<<1, ql, qr, edge);
    if(qr>mid) insert(x<<1|1, ql, qr, edge);
}

然后你想查在某一个时间段 他是否为二分图，那么就从根 到叶子 遍历，路上遇到的边都加进来。最后到了叶子之后就是在这个时间段 的图了。然后就可以扩展域并查集判断了。

好像又没怎么优化？别慌还有！线段树分治还没用到！

---

判断的时候就可以使用线段树分治了。

考虑到二分图的一个性质：如果你这个图不是二分图，那你后面不管怎么加边，他一定不是二分图。

我们遍历到一个段 ，因为存在这里的边是在整个时间段 都存在的，如果我们加一条边 的时候他报错，不是二分图了，那么就说明后面不管怎么加边，他都不是二分图了。他不是二分图这个结论已经被定死了。于是我们把这个区间 的所有 全部改成 No。

反之，如果加完了这个 区间都存在的所有边，他还是二分图，那么就可以考虑分治了。我们把它分为 和 两段，然后继续判断。如果判到了叶子节点 他还是二分图，那他在 这个时间段他是二分图的这个事实也坐实了。于是把这个点的答案改为 Yes。

这个时候，发现了一个问题：一个节点，有两个儿子。他遍历完了左儿子想遍历右儿子，很明显的要撤销左儿子遍历过的边。怎么撤销呢？

我们维护一个栈，当合并 的时候把这个记录加入栈里面。当遍历完毕了之后，就依据栈里面的记录，将他复原。因为是按秩，从 向 合并，所以栈里面就依序存储合并的两个点 和 ，再存储 的大小。这样撤销的时候就只需执行以下操作：

struct Cglg{
    int from, to, sizv;
}
void dellatest(){
    Cglg u = changelog[len--];
    // Cglg: Changelog
    fa[u.from] = u.from;
    siz[u.to] = u.sizv;
}

这样也就很明显的，不能路径压缩。所以找父亲的函数就只能这样：

int getfa(int x){
    while(x!=fa[x]) x = fa[x];
    return x;
}

于是就讲完了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, m, k;
namespace DSU{
    int fa[N<<1], siz[N<<1];
    struct Cglg{
        int from, to, sizv;
    }changelog[N<<1];
    int len;
    void init(){
        for(int i=1;i<=(n<<1);i++){
            fa[i] = i;
        }
        for(int i=1;i<=(n<<1);i++){
            siz[i] = 1;
        }
    }
    int getfa(int x){
        while(x!=fa[x]) x = fa[x];
        return x;
    }
    void merge(int u, int v){
        u = getfa(u), v = getfa(v);
        if(siz[u] > siz[v]) swap(u,v);
        if(u==v) return ;
        changelog[++len] = {u, v, siz[v]};
        fa[u] = v;
        siz[v] += siz[u];
    }
    void dellatest(){
        Cglg u = changelog[len--];
        fa[u.from] = u.from;
        siz[u.to] = u.sizv;
    }
    bool check(int x, int y){
        x = getfa(x), y =getfa(y);
        return (x==y);
    }
}
using namespace DSU;
typedef pair<int,int> pii;
#define fi first 
#define se second
bool ans[N];
namespace Seg_Tr{
    struct node{
        int l, r;
        vector<pii> val;
    }tr[N<<2];
    void build(int x, int l, int r){
        tr[x].l = l, tr[x].r = r;
        if(l==r) return ;
        int mid = l+r>>1;
        build(x<<1, l, mid);
        build(x<<1|1, mid+1, r);
    }
    void insert(int x, int ql, int qr, pii edge){
        int l = tr[x].l, r = tr[x].r;
        if(ql<=l&&r<=qr){
            tr[x].val.push_back(edge);
            return ;
        }
        int mid = l+r>>1;
        if(ql<=mid) insert(x<<1, ql, qr, edge);
        if(qr>mid) insert(x<<1|1, ql, qr, edge);
    }
    void solve(int x){
        int nowlen = len;
        int isbin = 1;
        for(pii now:tr[x].val){
            if(check(now.fi, now.se)){
                isbin = 0;
                // for(int i=tr[x].l;i<=tr[x].r;i++) ans[i] = 0;
                break;
            }
            merge(now.fi, n+now.se), merge(now.se, n+now.fi);
        }
        if(isbin){
            if(tr[x].l == tr[x].r) ans[tr[x].l] = 1;
            else{
                solve(x<<1), solve(x<<1|1);
            }
        }
        while(len > nowlen) dellatest();
    }
}
using namespace Seg_Tr;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>k;
    pii ed;
    int l, r;
    init();
    build(1, 1, k);
    for(int i=1;i<=m;i++){
        cin>>ed.fi>>ed.se>>l>>r;
        l++;
        if(l<=r) insert(1, l, r, ed);
    }
    solve(1);
    for(int i=1;i<=k;i++){
        cout<<((ans[i])?"Yes\n":"No\n");
    }
    return 0;
}

---

P5214

这道题其实和模板题差不多。但是之前我做到这里的时候有一个疑问：

我用的是 map 存储的每一条边开始出现的位置，最后有一些边是还没有被删的，那么怎么遍历他们把他们加进线段树呢？

这时，神奇的迭代器：iterator 出现了！！！

迭代器就是和名字一样，不止是 map，所有的 STL 容器都可以用 iterator 来遍历一遍。

而我们经常见到的：

vector<int> edge[N];
for(int v:edge[p])

就是一种简化了的迭代器。

迭代器原本的写法是这样的：

定义迭代器（这个类型要和被迭代的容器的类型完全相同！）

// typedef pair<int, int> pii;
map<pii, int> mp;
map<pii, int>::iterator it;

遍历容器则是这样的（以 map 为例）：

for(it = mp.begin();it!=mp.end();it++){
    cout<<"Key: Edge{"<<it->first.first<<", "<<it->first.second<<"}\n";
    cout<<"Value: "<<it->second<<'\n';
}

其中 ->first 是迭代器目前指向的 Key， ->second 是迭代器目前指向的 Value。

配合着这个就能完美加边了=ω=