题目大意：给定一张 n 个点的图，有 m 条边， T 个时间段，每条边只存在于 (st,ed] 这些时间段，求每个时间段内这个图是否是二分图
分治并查集大法好
定义 Solve(x,y,E) 为当前处理的区间为 [x,y] ， E 为所有存在时间为 [x,y] 的子集的边的集合
那么对于 E 中的每一条边 (u,v) ，讨论：
若当前边的存在时间为 [x,y] ，则在并查集上判断是否出现奇环
如果出现， [x,y] 内的所有时刻都一定不是二分图，输出答案即可
如果不出现，在并查集中连接 (u,v)
否则判断存在时间和 mid 的关系讨论扔进左区间还是右区间还是都扔进去
并查集不需要可持久化，只需要记录进行过的操作，在回溯的时候复原即可
注意并查集不要写路径压缩，因为路径压缩的优化是均摊的，均摊在分治这种树形结构上使用是无效的，只写按秩合并就行了
时间复杂度 O(mlog2n)
然而跑的比 O(mlogn) 的LCT还快是什么鬼……

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define M 100100 using namespace std; struct edge{ int x,y; int st,ed; edge() {} edge(int _,int __,int ___,int ____): x(_),y(__),st(___),ed(____) {} }; int n,m,T; int stack[M<<2],top; //若x<0 代表x的rank被加了1 //若x>0 表示x的父亲被修改了 namespace Union_Find_Set{ int fa[M],rank[M],a[M]; int Find(int x) { while(fa[x]!=x) x=fa[x]; return fa[x]=x; } int Distance(int x) { int re=0; while(fa[x]!=x&&fa[x]) re^=a[x],x=fa[x]; return re; } void Union(int x,int y,int z) { x=Find(x);y=Find(y); if(x==y) return ; if(rank[x]>rank[y]) swap(x,y); if(rank[x]==rank[y]) rank[y]++,stack[++top]=-y; fa[x]=y;a[x]=z;stack[++top]=x; } void Restore(int bottom) { while(top>bottom) { if(stack[top]<0) rank[-stack[top]]--; else fa[stack[top]]=stack[top],a[stack[top]]=0; top--; } } } void Divid_And_Conquer(int x,int y,vector
        
          &e) { using namespace Union_Find_Set; vector
         
          ::iterator it; int i,mid=x+y>>1,bottom=top; vector
          
            l,r; for(it=e.begin();it!=e.end();it++) { if(it->st==x&&it->ed==y) { int _x=Find(it->x); int _y=Find(it->y); int _z=Distance(it->x)^Distance(it->y)^1; if(_x!=_y) Union(_x,_y,_z); else if(_z&1) { for(i=x;i<=y;i++) puts("No"); Restore(bottom); return ; } } else if(it->ed<=mid) l.push_back(*it); else if(it->st>mid) r.push_back(*it); else l.push_back(edge(it->x,it->y,it->st,mid)),r.push_back(edge(it->x,it->y,mid+1,it->ed)); } if(x==y) puts("Yes"); else Divid_And_Conquer(x,mid,l),Divid_And_Conquer(mid+1,y,r); Restore(bottom); } int main() { //freopen("4025.in","r",stdin); //freopen("4025.out","w",stdout); int i; edge e; vector
           
             v; cin>>n>>m>>T; for(i=1;i<=n;i++) Union_Find_Set::fa[i]=i; for(i=1;i<=m;i++) { scanf("%d%d%d%d",&e.x,&e.y,&e.st,&e.ed); e.st++; if(e.st>e.ed) continue; v.push_back(e); } Divid_And_Conquer(1,T,v); return 0; }