线段树分治从入门到入门

· · 题解

从这个线段树分治板子题，从头整理一下线段树分治的一些重点。

首先看到本题，如果只有添加边一种操作的话，显然是可以用扩展域并查集维护的，如果不会可以翻到本文最后面有讲。

但是本题有删除边的操作，这就不能只用并查集维护了。

我们考虑一个 O(n^2) 的暴力（设 n,m 同阶），对每一个询问，找到有哪些边在这个询问时是存在的，然后直接在空并查集上加边，最后判断是否为二分图。

考虑这个暴力不足的地方：由于操作是对一个时间区间都存在，有一些边在下一个询问中仍然是存在的，但是我们将其全部删掉了。我们的并查集虽然不能支持删除边，但是可以撤销（可撤销并查集也见文末）！如果我们知道相对下一个询问，我们需要撤销哪些边，再加上哪些边，是不是可以优化复杂度呢？

线段树分治的思想

我们对时间（询问）建立一颗线段树，树的节点存的信息是【覆盖了这个区间的操作】。

考虑遍历整颗线段树，维护一颗可撤销并查集。当进入一个线段树的子节点时，在并查集上添加覆盖这个区间的边。然后继续递归子节点，直到叶子节点（对应的就是一个询问），统计对应的答案。回溯时，将这个节点加的边在并查集上撤销。

这样，递归到每一个叶子节点时，并查集中的边都是这个询问的完整状态。

分析复杂度，遍历线段树的时间是 O(n\log n) 的，总共 O(n) 个操作，每一个操作在线段树上最多覆盖 \log n 个节点，可撤销并查集由于不能使用路径压缩，所以按秩合并的复杂度是 O(\log n) 的，维护操作的复杂度是 O(n\log^2n) 的。

这就是线段树分治。

看到什么应该想到线段树分治？

比如本题：操作为删除或者添加边，也就是说一条边的影响范围是一个区间。同时在每一次操作后求答案（是否为二分图）。

实现

#include<bits/stdc++.h>
using namespace std;
struct BCJ //可撤销并查集
{
    int n;
    int fa[200010];
    int dep[200010];
    void init(int x)
    {
        n=x;
        for(int i=1;i<=2*n;i++)
        {
            fa[i]=i;
            dep[i]=1;
        }
    }
    int find(int x)
    {
        return x==fa[x]?x:find(fa[x]);
    }
    void merge(int x,int y,stack<int>&sta)
    {
        x=find(x),y=find(y);
        if(x==y)return;
        if(dep[x]<dep[y])swap(x,y);
        fa[y]=x;
        dep[x]=max(dep[x],dep[y]+1);
        sta.push(y);
    }
    void roll_back(stack<int>&sta)
    {
        while(!sta.empty())
        {
            int x=sta.top();
            sta.pop();
            fa[x]=x;
        }
    }
}bcj;
struct EDGE
{
    int x,y;
}edge[200010];
vector<int> tr[800010];
int n,m;
bitset<200010>ans;
void update(int now,int l,int r,int ll,int rr,int e)
{
    if(l>rr||r<ll)return ;
    if(ll<=l&&rr>=r)
    {
        tr[now].push_back(e); //操作标记
        return ;
    }
    int mid=l+r>>1;
    update(now<<1,l,mid,ll,rr,e);
    update(now<<1|1,mid+1,r,ll,rr,e);
}
void getans(int now,int l,int r)
{
    stack<int>sta;
    for(auto x:tr[now]) //加边
    {
        if(bcj.find(edge[x].x)==bcj.find(edge[x].y))
        {
            for(int i=l;i<=r;i++)
            {
                ans[i]=0;
            }
            bcj.roll_back(sta);
            return ;
        } //剪枝，如果在边没加完就已经冲突了，再加边也不可能成为二分图，于是整个区间都不可能成为答案。
        bcj.merge(edge[x].x,edge[x].y+n,sta);
        bcj.merge(edge[x].x+n,edge[x].y,sta);
    }
    if(l!=r) //非叶子节点继续递归
    {
        int mid=l+r>>1;
        getans(now<<1,l,mid);
        getans(now<<1|1,mid+1,r);
    }
    bcj.roll_back(sta);
}
map<pair<int,int>,int>mp;
int cnte=0;
signed main()
{
    ans.set();
    cin>>n>>m;
    bcj.init(n);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if(mp[{x,y}])
        {
            int from=mp[{x,y}];
            cnte++;
            edge[cnte].x=x,edge[cnte].y=y;
            update(1,1,m,from,i-1,cnte);
            mp[{x,y}]=0;
        }
        else
        {
            mp[{x,y}]=i;
        }
    }
    for(auto x:mp)
    {
        if(x.second)
        {
            cnte++;
            edge[cnte].x=x.first.first,edge[cnte].y=x.first.second;
            update(1,1,m,x.second,m,cnte);
        }
    }
    getans(1,1,m);
    for(int i=1;i<=m;i++)
    {
        cout<<(ans[i]?"YES\n":"NO\n");
    }
}

不知道谁的线段树分治题单，希望有用。

扩展域并查集

有很多形式，这里只讲维护二分图的。

考虑对于每一个真实的点，建立【反点】，并查集上点 x 和点 y 的反点连一条边，意义是点 x 不能和点 y 在二分图的同一个部。

真实的图中连一条边，说明两个点不能在一个部中，这时分别给对方的反点在并查集上连边，完成操作。

如果一次操作连接点 x 和点 y，但是并查集中 x 和 y 在一个树中，就不是二分图。

可撤销并查集

考虑并查集操作：把 x 指向 y，操作前 x,y 都是根节点，撤销一次操作就是把 x 指向自己。

撤销需要按操作的顺序来，也就是说需要用栈将进行的操作存下来，需要撤销的时候直接弹栈，令 fa_x\gets x 即可。

具体可以参考上面的代码理解。