线段树分治¶

例题 #1 二分图 /【模板】线段树分治¶

神犇有一个 \(n\) 个节点的图。

因为神犇是神犇，所以在 \(k\) 时间内有 \(m\) 条边会出现后消失。

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

这么简单的问题神犇当然会做了，于是他想考考你。

原 BZOJ4025。

\(n,k = 10^5\)，\(m = 2\times 10^5\)。\(1 \le x,y \le n\)，\(0 \le l \le r \le k\)。

思路¶

要做这道题首先要知道如何快速判断二分图。我们考虑关押罪犯这道题，里面使用扩展域并查集维护了图是否是二分图。

扩展域并查集

并查集

线段树分治维护操作序列

我们考虑每条边都在时间轴上的某个区间内有效，那么我们就可以类比线段树——把这条边在线段树上添加或修改。

这样我们把所有询问离线下来并且在线段树中做好修改，最后一次性处理。但是我们发现当我们处理完这个节点的子节点时，我们必须将并查集还原到处理之前的状态才可以递归处理其他节点，这时我们就需要支持撤销的并查集操作。

这样我们就不可以路径压缩了，因为这样我们在撤销时要修改很多的点的父亲。我们只好按秩合并（启发式合并），并且每个节点都只记录其真正的父亲，这样在撤销时只需要修改一个点的父亲即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long


#define rd read()
int read(){
    int xx=0,ff=1;
    char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') ff=-1;c=getchar();}
    while(c>='0'&&c<='9') xx=xx*10+(c-'0'),c=getchar();
    return xx*ff;
}
void write(int out){
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}


const int N=5e6+5;
const int M=5e5+5;
const int INF=1e9+5;
const int base=23;
const int MOD=19260817;

int n,m,k,fa[N],dep[N],top;
struct edge{
    int x,y;
}e[N];
struct node{
    int x,y,add;
}stk[N];

vector<int> t[N];

int find(int x){
    while(x != fa[x]) x = fa[x];
    return fa[x];
}
void merge(int x,int y){
    int fx = find(x),fy = find(y);
    if(dep[fx] > dep[fy]) swap(fx,fy);
    stk[++top] = (node){fx,fy,dep[fx] == dep[fy]};
    fa[fx] = fy;
    if(dep[fx] == dep[fy]) dep[fy]++;
}
void update(int u,int l,int r,int L,int R,int x){
    if(l > R || r < L) return;
    if(L <= l && r <= R) {t[u].push_back(x);return;}
    int mid = l + r >> 1;
    update(u<<1,l,mid,L,R,x);
    update(u<<1|1,mid+1,r,L,R,x);
}
void solve(int u,int l,int r){
    int ans = 1;
    int lst = top;
    for(int i = 0;i < t[u].size();i++){
        int a = find(e[t[u].at(i)].x);
        int b = find(e[t[u].at(i)].y);
        if(a == b){
            for(int k = l;k <= r;k++)
            printf("No\n");
            ans = 0;
            break;
        }
        merge(e[t[u].at(i)].x,e[t[u].at(i)].y+n);
        merge(e[t[u].at(i)].y,e[t[u].at(i)].x+n);
    }
    if(ans){
        if(l==r) printf("Yes\n");
        else {
            int mid = l+r>>1;
            solve(u<<1,l,mid);
            solve(u<<1|1,mid+1,r);
        }
    }
    while(top > lst){
        dep[fa[stk[top].x]] -= stk[top].add;
        fa[stk[top].x] = stk[top].x;
        top--;
    }
    return;
}

signed main(){
    n = rd;m = rd;k = rd;
    // cerr<<"OK";
    for(int i = 1;i <= m;i++){
        e[i].x = rd;e[i].y = rd;
        int l = rd+1,r = rd;
        update(1,1,k,l,r,i);
    }
    for(int i = 1;i <= 2*n;i++) fa[i] = i,dep[i] = 1;
    solve(1,1,k);
    return 0;
}