对时间分治，用启发式并查集维护一下，时间复杂度O(mlog^2n)，然而并查集常数极小，所以跑的比lct的O(mlogn)还快。

lct见http://wuzuofan.is-programmer.com/posts/89928.html 或者 http://c-sunshine.logdown.com

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<ctime>
#include<cmath>
using namespace std;

typedef pair<int, int> Pii;
typedef long long LL;
typedef long double db;
#define rep(_,A,B) for(_=A;_<=B;++_)
#define repi(_,A,B) for(register int _=A;_<=B;++_)
#define FOR(_,A) for(int _=h[A];_;_=next[_])
#define A first
#define B second
#define mp make_pair
char o;template<class O> void read(O&x){while(o=getchar(),o<'0'||o>'9');for(x=o^48;o=getchar(),o>='0'&&o<='9';)x=x*10+(o^48);}
const int L = 100005, M = 200005;

int n, m, T;
struct M{ int u, v, st, ed; } e[M];
int fa[L], d[L], a[L], q[M], top; 

Pii findx(int x) {
    int t = 0;
    for(; fa[x] != x; x = fa[x]) t ^= a[x];
    return mp(x, t);
}

void merge(int x, int y, int dep) {
     if(d[x] > d[y]) swap(x, y);
     if(d[x] == d[y]) ++d[y], q[++top] = -y;
     fa[x] = y, a[x] = dep, q[++top] = x;
}

void resume(int t) {
     for(; top != t; --top)
       if(q[top] > 0) fa[q[top]] = q[top], a[q[top]] = 0;
       else --d[-q[top]];
}

void init(void) {
     cin >> n >> m >> T;
     repi(i, 1, m) {
       read(e[i].u), read(e[i].v), read(e[i].st), read(e[i].ed), ++e[i].st;
       if(e[i].st > e[i].ed) --m, --i;
     }
     repi(i, 1, n) fa[i] = i, d[i] = 1;
}

void solve(int l, int r, int r0) {
     int now = top, mid = l + r >> 1, i, j;
     rep(i, 1, r0) if(e[i].st <= l && r <= e[i].ed) {
         Pii x = findx(e[i].u), y = findx(e[i].v);
         int fx = x.A, fy = y.A, dep = !(x.B ^ y.B);
         if(fx != fy) merge(fx, fy, dep);
         else if(dep){ while(l <= r) puts("No"), ++l;  resume(now); return ; }
         swap(e[r0--], e[i--]);
     }
     if(l == r) { puts("Yes"); return ; }
     for(i = 1, j = r0; i <= j; ++i)
       if(e[i].st > mid) swap(e[i--], e[j--]);
     solve(l, mid, j);
     for(i = 1, j = r0; i <= j; ++i)
       if(e[i].ed <= mid) swap(e[i--], e[j--]);
     solve(mid + 1, r, j);
     resume(now);
}

void work(void) {
     solve(1, T, m); 
}
int main(void) {
  freopen("4025.in","r",stdin), freopen("4025.out","w",stdout);
  init(), work(); return 0;
}