如果边不会消失，那么显然可以带权并查集做（然后发现自己不会写带权并查集）
但是每条边有消失时间。这样每一条边产生贡献的时间对应一段区间，故对时间轴建立线段树，将每一条边扔到线段树对应的点上。
然后遍历整棵线段树，每遍历到一个点将覆盖这个点对应区间的边全部加入带权并查集中，递归到叶子节点输出答案。回溯的时候把在这一个点加入的边从并查集中栈序撤销。
因为需要撤销所以并查集不能使用路径压缩，只能按秩合并。
#include#include #include #include //This code is written by Itstusing namespace std;inline int read(){ int a = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = a * 10 + c - 48; c = getchar(); } return a;}const int MAXN = 1e5 + 7;int N , M , T;#define PII pair < int , int >#define st first#define nd second#define mid ((l + r) >> 1)#define lch (x << 1)#define rch (x << 1 | 1)vector < PII > Edge[MAXN << 2];void addEd(int x , int l , int r , int L , int R , PII Ed){ if(l >= L && r <= R){ Edge[x].push_back(Ed); return; } if(mid >= L) addEd(lch , l , mid , L , R , Ed); if(mid < R) addEd(rch , mid + 1 , r , L , R , Ed);}struct node{ int fa , val , sz;}dsu[MAXN];PII find(int x){ if(dsu[x].fa == x) return PII(x , 0); PII t = find(dsu[x].fa); return PII(t.st , t.nd ^ dsu[x].val);}void solve(int x , int l , int r , bool f){ stack < int > stk; for(vector < PII > :: iterator t = Edge[x].begin() ; t != Edge[x].end() ; ++t){ int p = (*t).st , q = (*t).nd; PII M = find(p) , N = find(q); int m = M.st , n = N.st; if(m != n){ if(dsu[m].sz > dsu[n].sz) swap(n , m); dsu[n].sz += dsu[m].sz; dsu[m].fa = n; dsu[m].val = M.nd ^ N.nd ^ 1; stk.push(m); } else f &= (M.nd ^ N.nd); } if(l == r) puts(f ? "Yes" : "No"); else{ solve(lch , l , mid , f); solve(rch , mid + 1 , r , f); } while(!stk.empty()){ int t = stk.top(); stk.pop(); dsu[dsu[t].fa].sz -= dsu[t].sz; dsu[t].val = 0; dsu[t].fa = t; }}int main(){#ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout);#endif N = read(); M = read(); T = read(); for(int i = 1 ; i <= M ; ++i){ int a = read() , b = read() , l = read() , r = read(); if(l < r) addEd(1 , 1 , T , l + 1 , r , PII(a , b)); } for(int i = 1 ; i <= N ; ++i){ dsu[i].fa = i; dsu[i].sz = 1; } solve(1 , 1 , T , 1); return 0;}