P5787 二分图 /【模板】线段树分治

需要不少前置知识的一道题

一眼看上去是个LCT，复杂度$O(n\log n)$但代码能力要求较高

这里我们介绍一种比较简单的处理时间轴问题的离线算法：线段树分治

题解：

首先必须要知道二分图的判定方法：图中不存在任何奇环

这是个经典问题，可以用并查集解决，即对于每个点拆成奇数偶数两个版本，对于边$(u,v)$我们把它拆成(奇u,偶v)和(偶u,奇v)，然后再按正常并查集判环，此时判出来的环一定是奇环

其次，这还要求是一个可撤销的并查集，所以为了稳定的复杂度要把路径压缩改为按秩合并，并额外记录一个操作栈$s$，记录每次操作后，对哪个点产生了怎样的影响（包括秩的增大与父亲的改变）

有了以上这些前置知识后，再来看这道题，发现纯粹对每个时间节点单独进行刷新、计算，肯定是会T的，那能不能在相邻时间点的基础上保留一些不需要刷新的信息呢？

这就要用到线段树分治了

考虑在（时间轴）线段树上把每条边的作用域拆成一条条尽可能长的线段，对每条线段记录上面有哪些边存在

在从上到下递归这棵线段树时，我们要对当前访问到的线段上的存在边做“添加”操作，把它们加到可撤销并查集上，假如某一时刻判出奇环了，就可以直接回溯，并输出线段长个”no”，因为这下面额外添加的边无论怎么做都是无事于补；否则就要一直往下递归，如果到了叶子结点，就说明这个时间点无论加了那条边都是合法的，输出一个”yes”并回溯

在从下往上回溯时，我们要用可撤销并查集的“撤销操作”去除掉底层边对其它线段的影响（因为它高度比较低，比较菜，影响力较弱）

复杂度可能比较难分析，其实是$O(m\log n\log k)$的

（个人认为难度全在于内个可撤销并查集）

为啥可撤销并查集用栈是正确的的呢？因为每一层的连边操作都会在本层撤销掉，因此只要考虑本层的加边顺序就好了

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

#define pii pair<int,int>
#define x first
#define y second

const int N=1e5+5,M=2e5+5;
int f[N<<1],d[N<<1],n,m,k,u[M],v[M];
stack<pii> s;
vector<int> e[N<<2];

void up(int x,int l,int r,int p,int q,int id){
    if(p<=l&&r<=q){
        e[x].push_back(id); //记录这条线段上有哪些边存在
        return ;
    }
    int mid=l+r>>1;
    if(p<=mid) up(x<<1,l,mid,p,q,id);
    if(q>mid) up(x<<1|1,mid+1,r,p,q,id);
}

int getf(int x){
    while(x^f[x]) x=f[x];
    return x;
}

void merge(int x,int y){
    if(x==y) return ;
    if(d[x]>d[y]) swap(x,y); //按秩合并
    s.push(pii(x,d[x]==d[y]));
    f[x]=y;
    d[y]+=d[x]==d[y];
}

void dfs(int x,int l,int r){
    bool flag=1;
    int last=s.size();
    for(int i=0;i<e[x].size();i++){
        int now=e[x][i],u=getf(::u[now]),v=getf(::v[now]); //双冒号的意思是全局变量，真是高效呢~
        if(u==v){
            for(int j=l;j<=r;j++) puts("No"); //有奇环出现，不是二分图
            flag=0;
            break;
        }
        merge(getf(::u[now]+n),v); //合并
        merge(getf(::v[now]+n),u);
    }
    if(flag){ //这条线段上的边都是合法的，可以继续递归
        if(l==r) puts("Yes"); //到底了就是合法的，是个二分图
        else{
            int mid=l+r>>1;
            dfs(x<<1,l,mid); //往下递归
            dfs(x<<1|1,mid+1,r);
        }
    }
    while(s.size()>last){ //撤销操作
        d[f[s.top().x]]-=s.top().y;
        f[s.top().x]=s.top().x;
        s.pop();
    }
}

signed main(){
    read(n);read(m);read(k);
    for(int i=1,l,r;i<=m;i++){
        read(u[i]);read(v[i]);read(l);read(r);
        if(l^r) up(1,1,n,l+1,r,i); //小trick，本来这条边应该是在区间[l,r)存在，但为了让下标大于0，我们统一加一改为(l,r]
    }
    for(int i=1;i<=n+n;i++) f[i]=i;
    dfs(1,1,k);
}
赏

fighter