线段树分治
- 对时间分治
cpp
struct SegmentTree{
struct Node{
int l,r;
vector<array<int,2>> a;
};
vector<Node> t;
void init(int n){
t=vector<Node>(n<<2);
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void modify(int p,int l,int r,int x,int y){
if(l<=t[p].l&&r>=t[p].r){
t[p].a.push_back({x,y});
return;
}
int mid=t[p].l+t[p].r>>1;
if(l<=mid)modify(p<<1,l,r,x,y);
if(r>mid)modify(p<<1|1,l,r,x,y);
}
void dfs(int p,int l,int r){
bool g=0;
int tot=dsu.tot;
for(auto &[u,v]:t[p].a){
if(dsu.same(u,v)){
for(int i=l;i<=r;i++)cout<<"No\n";
g=1;
break;
}
dsu.merge(u,v+n,1);
dsu.merge(v,u+n,1);
}
if(!g){
if(l==r){
cout<<"Yes\n";
return;
}
int mid=l+r>>1;
dfs(p<<1,l,mid);
dfs(p<<1|1,mid+1,r);
}
dsu.back(tot);
}
} seg;
void solve(){
int m,k;
cin>>n>>m>>k;
seg.init(k);
seg.build(1,1,k);
dsu.init(2*n+1);
for(int i=1;i<=m;i++){
int x,y,l,r;
cin>>x>>y>>l>>r;
seg.modify(1,l+1,r,x,y);
}
seg.dfs(1,1,k);
}