首先对时间分治，每个节点表示一个时间的区间$[l, r]$

然后对于每个节点记录一个可以撤销的并查集，维护图的信息即可

(这里的并查集不用路径压缩，只要按秩合并，这样子可以保证单次操作的时间复杂度是$O(logn)$的)

我去啊。。。把边分类这一段代码调的我QAQ了。。。代码能力太弱QAQQQ

 

1 /**************************************************************  2     Problem: 4025  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:4344 ms  7     Memory:6668 kb  8 ****************************************************************/  9   10 #include 
      
        11 #include 
       
         12   13 using namespace std; 14 const int N = 1e5 + 5; 15 const int M = 2e5 + 5; 16   17 inline int read(); 18   19 struct edge { 20     int x, y, st, ed; 21   22     inline void get() { 23         x = read(), y = read(); 24         st = read() + 1, ed = read(); 25     } 26 } e[M]; 27   28 int n, m, time; 29   30 namespace set { 31     int fa[N], d[N], a[N]; 32     int s[N << 2], top = 0; 33       34     int find(int x) { 35         while (fa[x] != x) x = fa[x]; 36         return x; 37     } 38     int dep(int x) { 39         static int res; 40         for (res = 0; fa[x] != x; x = fa[x]) 41             res ^= a[x]; 42         return res; 43     } 44       45     void set_union(int x, int y, int _d) { 46         if (d[x] > d[y]) swap(x, y); 47         if (d[x] == d[y]) ++d[y], s[++top] = -y; 48         fa[x] = y, a[x] = _d, s[++top] = x;  49     } 50       51     void set_resume(int t) { 52         for (; top != t; --top) 53             if (s[top] < 0) --d[-s[top]]; 54             else fa[s[top]] = s[top], a[s[top]] = 0; 55     } 56 } 57 using namespace set; 58   59 void work(int l, int r, int m) { 60     int mid = l + r >> 1, now = top; 61     int i, j, fx, fy, _d; 62     for (i = 1; i <= m; ++i) 63         if (e[i].st <= l && r <= e[i].ed) { 64             fx = find(e[i].x), fy = find(e[i].y), _d = !(dep(e[i].x) ^ dep(e[i].y)); 65             if (fx != fy) set_union(fx, fy, _d); 66             else if (_d) { 67                 while (l <= r) 68                     puts("No"), ++l; 69                 set_resume(now); 70                 return; 71             } 72             swap(e[m--], e[i--]); 73         }; 74     if (l == r) puts("Yes"); 75     else { 76         for (i = 1, j = m; i <= j; ++i) 77             if (e[i].st > mid) swap(e[j--], e[i--]); 78         work(l, mid, j); 79         for (i = 1, j = m; i <= j; ++i) 80             if (e[i].ed <= mid) swap(e[j--], e[i--]); 81         work(mid + 1, r, j); 82     } 83     set_resume(now); 84 } 85   86 int main() { 87     int i; 88     n = read(), m = read(), time = read(); 89     for (i = 1; i <= n; ++i) 90         fa[i] = i, d[i] = 1, a[i] = 0; 91     for (i = 1; i <= m; ++i) e[i].get(); 92     for (i = 1; i <= m; ++i) 93         if (e[i].st > e[i].ed) swap(e[i--], e[m--]); 94     work(1, time, m); 95     return 0; 96 } 97   98 inline int read() { 99     static int x, sgn;100     static char ch;101     x = 0, sgn = 1, ch = getchar();102     while (ch < '0' || '9' < ch) {103         if (ch == '-') sgn = -1;104         ch = getchar();105     }106     while ('0' <= ch && ch <= '9') {107         x = x * 10 + ch - '0';108         ch = getchar();109     }110     return sgn * x;111 }