```cpp
#include <cstdio>
#include <stack>
#include <random>
#include <iostream>
#define sd std::
#define UP(i,s,e) for(auto i=s; i<e; ++i)
constexpr int N=1e5, M=2e5, K=1e5;
sd mt19937 rdna(0x383494);
struct Edge{ int from, to; Edge(int f, int t):from(f), to(t){}};
namespace dsu{ // }{{{
int fa[N*2], pri[N*2];
void init(int x){ UP(i, 0, x*2) fa[i] = i, pri[i] = rdna(); }
int getfa(int x){ return fa[x]==x?x:getfa(fa[x]); }
sd stack<int> dids;
void undo(){ {fa[dids.top()]=dids.top();} dids.pop();}
void merge(int x, int y){
x=getfa(x), y=getfa(y);
if(pri[x] > pri[y]) fa[y]=x, dids.push(y);
else fa[x]=y, dids.push(x);
}
} // {}}}
namespace segt{ // }{{{
struct Node{
Node *ls, *rs;
sd vector<Edge> es;
int l, r;
} bf[K*2];
Node *nnod(){ static int cnt=0; return &bf[cnt++]; }
void build(Node *root, int l, int r){
root->l = l, root->r = r;
if(l == r-1) return;
int mid = (l+r)/2;
root->ls = nnod(), root->rs = nnod();
build(root->ls, l, mid);
build(root->rs, mid, r);
}
void insert(Node *root, int l, int r, Edge e){
if(root->l == l && root->r == r){ root->es.push_back(e); return; }
int segmid = (root->l+root->r)/2;
if(l<segmid) insert(root->ls, l, sd min(r, segmid), e);
if(r>segmid) insert(root->rs, sd max(l, segmid), r, e);
}
} // {}}}
namespace m{ // }{{{
int in, im, ik;
segt::Node *segroot;
void dfs(segt::Node *root);
void work(){
sd cin >> in >> im >> ik;
segroot = segt::nnod();
dsu::init(in);
segt::build(segroot, 0, ik);
UP(i, 0, im){
int x, y, l, r;
sd cin >> x >> y >> l >> r;
x--, y--;
if(l != r) segt::insert(segroot, l, r, Edge(x, y));
}
dfs(segroot);
}
using namespace segt;
void dfs(Node *root){
UP(i_, 0u, root->es.size()){
auto i = root->es[i_];
dsu::merge(i.from, i.to+in);
dsu::merge(i.from+in, i.to);
if(dsu::getfa(i.from) == dsu::getfa(i.from+in) ||
dsu::getfa(i.to) == dsu::getfa(i.to+in)) {
UP(j, root->l, root->r) sd cout << "No\n";
UP(j, 0u, i_+1) dsu::undo();
return;
}
}
if(root->r-1 == root->l){
bool flg = true;
UP(i, 0, in) if(dsu::getfa(i) == dsu::getfa(i+in)){
flg = false;
}
sd cout << (flg ? "Yes\n" : "No\n");
} else {
dfs(root->ls);
dfs(root->rs);
}
UP(i, -(int)root->es.size(), 0){
dsu::undo();
dsu::undo();
}
}
} // {}}}
int main(){ sd ios::sync_with_stdio(0); sd cin.tie(0); m::work(); return 0;}
```
by x383494 @ 2023-07-09 17:09:03
并查集写法见[这个帖子](https://www.luogu.com.cn/discuss/407988)
by x383494 @ 2023-07-09 17:17:33
找到原因了 是这里写假了
```cpp
if(root->r-1 == root->l){
bool flg = true;
UP(i, 0, in) if(dsu::getfa(i) == dsu::getfa(i+in)){
flg = false;
}
sd cout << (flg ? "Yes\n" : "No\n");
}
```
警钟.jpg
by x383494 @ 2023-07-09 20:26:52