题目：

分析：

定理：一个图是二分图的充要条件是不存在奇环。

先考虑一个弱化的问题：保证所有边出现的时间段不会交叉，只会包含或相离。

还是不会？再考虑一个更弱化的问题：边只会出现不会消失。

当加边的时候，若\((u,v)\)不连通：一定不会构成奇环，将它加入。

若\((u,v)\)已经联通，则不加入这条边，而是查询\(u\)和\(v\)两点间的距离。若为偶数则加上这条边后会形成奇环。一个奇环不可能分成数个偶环，所以从此以后都不再是二分图。若为奇数则直接忽略这条边，因为如果将来某条边会与这条边形成奇环，则用当前\(u\)到\(v\)之间的路径（长度为奇数）替代这条边（长度为\(1\)）同样也会形成奇环。

按照上述做法，最终我们会造出原图的一棵生成树。

用带权并查集维护连通性和两点间距离的奇偶性。记录每个结点到它并查集上的父亲的距离（注意并查集的形态不一定和原树相同。加入边\((u,v)\)时在并查集上连接的是它们所在集合的根\(f(u)\)和\(f(v)\)）。

当加入边\((u,v)\)时，设\(u\)和\(v\)所在并查集的根为\(x\)和\(y\)，要把\(x\)合并进\(y\)，\(x\)的父亲被赋值成\(y\)。脑补一下此时\(x\)到\(y\)的路径是\(x\)到\(u\)，边\((u,v)\)，然后\(v\)到\(y\)，所以暴力爬链分别求出\(u\)和\(v\)到根的距离，异或起来再异或\(1\)就是\(x\)到它的父亲\(y\)的距离。

查询时把两点到根距离异或起来就是它们之间距离的奇偶性。（树上两点间路径是唯一的，多余的路径被走了偶数次不影响奇偶性。）

如果边会消失呢？删除一条已经被加入的边时，由于保证不存在出现时间交叉的情况，删除的一定是最晚加入的边。因此把对并查集的每次修改都存到一个栈中，撤销的时候按修改顺序的逆序复原即可。这种神奇的数据结构叫“可撤销并查集”

为了保证\(O(\log n)\)的时间复杂度，需要按秩合并。同时由于要可撤销，不能路径压缩破坏树形。放上可撤销并查集的代码。

namespace UFS{    int fa[N], top, rk[N];    bool dis[N];    struct node    {        int x, y, f, r;        bool d;    }stack[N];    int f(const int x)    {        return x == fa[x] ? x : f(fa[x]);    }    inline void init()    {        for (int i = 1; i <= n; i++)            fa[i] = i, dis[i] = 0, rk[i] = 1;    }    inline bool dist(int x)    {        return x == fa[x] ? dis[x] : dist(fa[x]) ^ dis[x];    }    inline void merge(const int u, const int v)    {        int x = f(u), y = f(v);        if (rk[x] > rk[y])            swap(x, y);        int tmp = fa[x];        stack[top++] = (node){x, y, tmp, rk[y], dis[x]};        if (rk[x] == rk[y])            ++rk[y];        dis[x] ^= dist(u) ^ dist(v) ^ 1;        fa[x] = y;    }    inline void undo(const int bck)    {        while (top > bck)        {            fa[stack[top - 1].x] = stack[top - 1].f;            rk[stack[top - 1].y] = stack[top - 1].r;            dis[stack[top - 1].x] = stack[top - 1].d;            --top;        }    }}

考虑原问题。可以把每条边的出现时间拆成若干个区间，使这些区间互不交叉。然而，如果直接贪心地拆，这些区间的总数会被极端数据卡到\(m^2\)级别（如果所有边出现的区间均为\([k,k+m](1\leq k \leq m)\)，则第\(k\)条边将被分成\(k\)个区间，共有\(\frac{m(m+1)}{2}\)个区间）。

这种方式的缺陷在于边的顺序不够灵活。比如上述极端数据中的第\(m\)条边，在\([m+1,2m]\)这个区间中每个时刻都要被删一次再加入一次。如果把它第一个加入（即放在撤销栈的底部），就省了很多操作。

这里引入“线段树分治”。建立一棵线段树，每个结点记录哪些边能完全覆盖这个结点所代表区间（不重复记录。即如果一个结点记录了边\(e\)，那么它子树上的结点都不必记录\(e\)）。这样每条边最多分成\(\log T\)个区间。最后深搜线段树，搜到一个结点时加入这个结点记录的所有边，回溯时撤销。如果到叶子结点仍然没有出现奇环，则此时刻是二分图。可以参考代码理解。每个边最多被加入或撤销\(\log T\)次，每次加入需要\(\log m\)时间，总复杂度\(O(n\log^2n)\)。

代码：

一个优化：搜到一个结点时如果已经是二分图了，就不必再往下搜。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;namespace zyt{    template
        
             inline void read(T &x)    {        bool f = false;        char c;        x = 0;        do            c = getchar();        while (c != '-' && !isdigit(c));        if (c == '-')            f = true, c = getchar();        do            x = x * 10 + c - '0', c = getchar();        while (isdigit(c));        if (f)            x = -x;    }    template
         
           inline void write(T x) { static char buf[20]; char *pos = buf; if (x < 0) x = -x; do *pos++ = x % 10 + '0'; while (x /= 10); while (pos > buf) putchar(*--pos); } inline void write(const char *const s) { printf("%s", s); } const int N = 1e5 + 10, M = 2e5 + 10, B = 17; int n, m, T; namespace UFS { int fa[N], top, rk[N]; bool dis[N]; struct node { int x, y, f, r; bool d; }stack[N]; int f(const int x) { return x == fa[x] ? x : f(fa[x]); } inline void init() { for (int i = 1; i <= n; i++) fa[i] = i, dis[i] = 0, rk[i] = 1; } inline bool dist(int x) { return x == fa[x] ? dis[x] : dist(fa[x]) ^ dis[x]; } inline void merge(const int u, const int v) { int x = f(u), y = f(v); if (rk[x] > rk[y]) swap(x, y); int tmp = fa[x]; stack[top++] = (node){x, y, tmp, rk[y], dis[x]}; if (rk[x] == rk[y]) ++rk[y]; dis[x] ^= dist(u) ^ dist(v) ^ 1; fa[x] = y; } inline void undo(const int bck) { while (top > bck) { fa[stack[top - 1].x] = stack[top - 1].f; rk[stack[top - 1].y] = stack[top - 1].r; dis[stack[top - 1].x] = stack[top - 1].d; --top; } } } int ecnt, head[1 << (B + 1)]; bool ans[N]; struct edge { int to, next; }e[M * 18]; struct ed { int u, v, st, ed; }arr[M]; void add(const int a, const int b) { e[ecnt] = (edge){b, head[a]}, head[a] = ecnt++; } namespace Segment_Tree { void insert(const int rot, const int lt, const int rt, const int ls, const int rs, const int x) { if (ls <= lt && rt <= rs) { add(rot, x); return; } int mid = (lt + rt) >> 1; if (ls <= mid) insert(rot << 1, lt, mid, ls, rs, x); if (rs > mid) insert(rot << 1 | 1, mid + 1, rt, ls, rs, x); } void solve(const int rot, const int lt, const int rt) { using namespace UFS; int bck = top; bool flag = true; for (int i = head[rot]; ~i; i = e[i].next) { int now = e[i].to, x = f(arr[now].u), y = f(arr[now].v); if (x == y && !(dist(arr[now].u) ^ dist(arr[now].v))) { flag = false; break; } else if (x != y) merge(arr[now].u, arr[now].v); } if (flag) { if (lt == rt) ans[lt] = true; else { int mid = (lt + rt) >> 1; solve(rot << 1, lt, mid); solve(rot << 1 | 1, mid + 1, rt); } } undo(bck); } } int work() { using namespace Segment_Tree; read(n), read(m), read(T); UFS::init(); memset(head, -1, sizeof(head)); for (int i = 1; i <= m; i++) { read(arr[i].u), read(arr[i].v), read(arr[i].st), read(arr[i].ed); insert(1, 1, T, arr[i].st + 1, arr[i].ed, i); } solve(1, 1, T); for (int i = 1; i <= T; i++) if (ans[i]) write("Yes\n"); else write("No\n"); return 0; }}int main(){ return zyt::work();}