线段树分治的本质比较简单，一句话就可以说完：
线段树分治就是对时间维建线段树，将时间维上的区间操作在线段树上标记永久化。
P5787 二分图 /【模板】线段树分治
动态维护图是否是二分图可以通过 扩展域并查集 简单维护。（事实上这道题的难点可能在这个上面）
然后我们就将插入边的操作放到时间维的线段树上，然后去做类似 dfs 的查询即可。
具体的，进入线段树上一个点我们先将所有挂在当前点的连边操作做了，然后递归进儿子即可。如果已经到儿子了那么就判断当前图是否是二分图即可。
处理完儿子后就回溯情况，将边和维护的黑白点在同一个连通块内的点的个数全部回溯回去即可。
code
一个小剪枝是如果在一个非叶子节点图已经不是二分图了那么再连边也一定不可能变成二分图，因此可以直接返回。但是记得要在所有返回前都完整回溯，比如剪枝前要回溯，叶子节点记录完答案后要回溯。
点击查看代码
#include<bits/stdc++.h>
bool Mbe;
using namespace std;
#define ll long long
//namespace FIO{
// template<typename P>
// inline void read(P &x){P res=0,f=1;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}x=res*f;}
// template<typename Ty,typename ...Args>
// inline void read(Ty &x,Args &...args) {read(x);read(args...);}
// inline void write(ll x) {if(x<0ll)putchar('-'),x=-x;static int sta[35];int top = 0;do {sta[top++] = x % 10ll, x /= 10ll;} while (x);while (top) putchar(sta[--top] + 48);}
//}
//using FIO::read;using FIO::write;
const int N=1e5+7;
#define pii pair<int,int>
int n,m,k;
namespace uni{int fa[N<<1],siz[N<<1],cnt=0,top=0;pii stk[N<<1];void init(){for(int i=1;i<=n<<1;i++)fa[i]=i,siz[i]=1;}int find(int x){return fa[x]==x?x:find(fa[x]);} int oth(int x){return x>n?x-n:x+n;}void merge(int x,int y){x=find(x),y=find(y);if(x==y){return;}//cnt++; //只要需要判黑白染色即可！！！因为可以有偶环！！！if(siz[x]>siz[y])swap(x,y);stk[++top]={y,x}; //x 连向 yfa[x]=y;siz[y]+=siz[x];cnt+=(find(x)==find(oth(x)))+(find(y)==find(oth(y)));}void split(){ //去掉栈顶的连边int y=stk[top].first,x=stk[top].second;siz[y]-=siz[x];fa[x]=x;top--;}
}
using namespace uni;
namespace sgt_part{vector<pii>tag[N<<2];int ans[N];#define ls (u<<1)#define rs (u<<1|1)#define mid ((l+r)>>1)void modify(int u,int l,int r,int ql,int qr,pii x){if(ql<=l&&r<=qr){tag[u].push_back(x);return;}if(ql<=mid)modify(ls,l,mid,ql,qr,x);if(qr>mid)modify(rs,mid+1,r,ql,qr,x);}void query(int u,int l,int r){int lstcnt=cnt,lsttop=top;for(auto [u,v]:tag[u]){merge(u,v+n),merge(u+n,v);}if(l==r){ans[l]=(cnt==0);cnt=lstcnt;while(top>lsttop)split();return;}if(cnt!=0){cnt=lstcnt;while(top>lsttop)split();return;}query(ls,l,mid),query(rs,mid+1,r);cnt=lstcnt;while(top>lsttop)split();}
}
using namespace sgt_part;
bool Med;
signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//freopen(".in","r",stdin);//freopen(".out","w",stdout);cin>>n>>m>>k;init();for(int i=1,u,v,l,r;i<=m;i++){cin>>u>>v>>l>>r;l++;if(l>r)continue;modify(1,1,k,l,r,{u,v});}query(1,1,k);for(int i=1;i<=k;i++)cout<<(ans[i]?"Yes\n":"No\n");cerr<<'\n'<<1e3*clock()/CLOCKS_PER_SEC<<"ms\n";cerr<<'\n'<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";return 0;
}