二分图/分治

二分图/分治
我们按时间建一棵线段树，线段树每个叶子节点需要能表示出该时刻有边的情况。

就比如说我要修改红色的那个区间。
只需要修改 红x 的结点，在访问的时候只要把从叶子节点到根节点的路径上的加边情况加一起就可以了。
那问题在于怎么判断是不是二分图呢？
可参考关押罪犯
大概就是A不能和B在同一边,B不能和C在同一边,在这种情况下A,C姑且只能在一边。
所以也就是B和所有不能和A在同一边的 在同一边。
A也同理，和所有不能和B在同一边的 在同一边。

这时怎么去求解每个叶子节点的加边情况呢？
可以在线段树上遍历（dfs），然后暴力加边（在并查集内），同时也要撤销一些操作。
我们当然不能去写一些什么主席树+并查集来维护可持久化并查集。
所以只要用一个按秩合并的并查集即可。
按秩合并就是类似，这样：

B比A长，所以A要认B做爹。因为这么做才会让这个并查集更平衡，也就是更短（更扁）。
如果A,B一样长，那么B的长度因为加了一条边（红边）所以B的长度+1。
其他情况B长度不变。
而撤销也很简单，就是如果操作是A要认B做爹，撤销就是把A,B长度还原，把A的爹设成自己。
这里一定要逆着操作顺序!!!

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x)
{
    char c=getchar();x=0;
    while(c>'9'||c<'0') c=getchar();
    while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
}
struct seg
{
    vector<pair<int,int> >a;
    int l,r;
}t[401000];
int fa[201000];
inline void build(int pos,int l,int r)
{
    t[pos].l=l;t[pos].r=r;
    if(l==r) return ;
    int mid=l+r>>1;
    build(pos<<1,l,mid);
    build(pos<<1|1,mid+1,r);
}
inline void modify(int pos,int x,int y,pair<int,int> z)
{
    if(x<=t[pos].l&&t[pos].r<=y)
    {
        t[pos].a.push_back(z);
        return ;
    }
    int mid=t[pos].l+t[pos].r>>1;
    if(y<=mid) modify(pos<<1,x,y,z);
    else if(x>mid) modify(pos<<1|1,x,y,z);
    else modify(pos<<1,x,y,z),modify(pos<<1|1,x,y,z);
}
//以上均为线段树
int n,m,T;
int x,y,a,b,d[201000];
bool f;
inline int getroot(int x)
{
    if(x==fa[x]) return x;
    return getroot(fa[x]);
}
stack<pair<int,int> >s;
inline void merge(int x,int y)
{
    if(x==y) return ;
    if(d[x]>d[y]) swap(x,y);
    s.push(make_pair(x,d[x]==d[y]));
    fa[x]=y;
    d[y]+=(d[x]==d[y]);
}
inline void dfs(int pos)
{
    int sz=s.size();
    bool f=0;
    for(int i=0;i<t[pos].a.size();i++)
    {
        int x=t[pos].a[i].first,y=t[pos].a[i].second;
        int rtx=getroot(x),rty=getroot(y);
        if(rtx==rty)
        {
            f=1;
            for(int j=t[pos].l;j<=t[pos].r;j++)
                puts("No");
            break;
        }
        merge(rtx,getroot(y+n));
        merge(rty,getroot(x+n));
    }
    if(f==0)
    {
        if(t[pos].l==t[pos].r) 
        {
            puts("Yes");
            return ;
        }
        dfs(pos<<1);
        dfs(pos<<1|1);
    }
    while(s.size()>sz)
    {
        d[fa[s.top().first]]-=s.top().second;
        fa[s.top().first]=s.top().first;
        s.pop();    
    }   
}

int main()
{
    #ifdef _WIN32
    freopen("b4025.in","r",stdin);
    freopen("b4025.out","w",stdout);
    #endif
    read(n),read(m),read(T);
   // T++;    
    build(1,1,T);
    for(int i=1;i<=2*n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        read(x),read(y),read(a),read(b);
        a++;
        if(a>b) continue;
        modify(1,a,b,make_pair(x,y));
    }
    dfs(1);
}