1. 题目

传送门=￣ω￣=

2. 题解

好神啊 QwQ

首先二分图就是没有奇环的图

因此如果只有加边的话可以用带权并查集维护两点之间的路径奇偶性。

因为存在删边操作因此我们需要对时间分治。

对于分治的时间区间为 $[l, r]$的情况，枚举每一条存在时间包含在 $[l, r]$的边，设其存在时间为 $[s, t]$，连接点 $u$与点 $v$

如果 $l=s$且 $r=t$，就在并查集上查询 $u,v$的连通性，如果不连通就在并查集里连通他们，否则的话判断两点间路径的奇偶性，如果为偶数则说明当前这条边会导致奇环的出现，也就说明 $[l, r]$这段时间的答案都为 No。

如果 $[s, t]$是包含在 $[l, r]$里的（指真子集，即 $[s, t] \not = [l, r]$），就递归分治处理，判断是放到 $[l, mid]$里还是放到 $[mid + 1, r]$里还是把 $[s, t]$在 $mid$处切开分别下放到两个区间里。

回溯的时候撤销当前区间对并查集的修改即可，用一个栈来保存历史操作即可，并且用按秩合并优化。

因为可以证明每条边最多出现 $log$级别次，因此整体复杂度是 $O(m log _ 2 n)$的。

代码：

#include <bits/stdc++.h>

#define NS (100005)
#define MS (200005)
#define LGS (40)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, bool> PIB;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct Edge {int u, v, s, t;} E[MS * LGS], L[MS], R[MS];

int n, m, T, cnt, fa[NS], Rank[NS];

bool v[NS];

stack<int> st;

PIB findf(int a)
{
    if (fa[a] == a) return PIB(a, 0);
    PIB tmp = findf(fa[a]);
    tmp.SEC ^= v[a];
    return tmp;
}

void Merge(int a, int b, int c)
{
    if (a == b) return;
    if (Rank[a] > Rank[b]) swap(a, b);
    else if (Rank[a] == Rank[b]) Rank[b]++, st.push(-b);
    fa[a] = b, v[a] = c, st.push(a);
}

void Undo(int cel)
{
    while (st.size() > cel)
    {
        if (st.top() > 0) fa[st.top()] = st.top(), v[st.top()] = 0;
        else Rank[-st.top()]--;
        st.pop();
    }
}

void Run(int l, int r, int p, int q)
{
    if (p > q)
    {
        for (int i = l; i <= r; i += 1) puts("Yes");
        return;
    }
    int cel = st.size(), mid = (l + r) >> 1, c1 = 0, c2 = 0;
    for (int i = p; i <= q; i += 1)
    {
        if (l == E[i].s && E[i].t == r)
        {
            PIB t1 = findf(E[i].u), t2 = findf(E[i].v);
            if (t1.FIR != t2.FIR) Merge(t1.FIR, t2.FIR, t1.SEC ^ t2.SEC ^ 1);
            else if (t1.SEC ^ t2.SEC ^ 1)
            {
                for (int j = l; j <= r; j += 1) puts("No");
                Undo(cel);
                return;
            }
        }
        else if (E[i].t <= mid) L[++c1] = E[i];
        else if (E[i].s > mid) R[++c2] = E[i];
        else L[++c1] = E[i], R[++c2] = E[i], L[c1].t = mid, R[c2].s = mid + 1;
    }
    if (l == r) puts("Yes");
    else
    {
        int x1 = cnt + 1, y1, x2, y2;
        for (int i = 1; i <= c1; i += 1) E[++cnt] = L[i];
        y1 = cnt, x2 = cnt + 1;
        for (int i = 1; i <= c2; i += 1) E[++cnt] = R[i];
        y2 = cnt, Run(l, mid, x1, y1), Run(mid + 1, r, x2, y2);
    }
    Undo(cel);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(T);
    for (int i = 1; i <= n; i += 1) fa[i] = i, v[i] = 0;
    for (int i = 1; i <= m; i += 1)
    {
        IN(E[++cnt].u), IN(E[cnt].v), IN(E[cnt].s), IN(E[cnt].t);
        E[cnt].s++;
        if (E[cnt].s > E[cnt].t) cnt--;
    }
    Run(1, T, 1, cnt);
    return 0;
}