C131【模板】线段树分治 P5787 线段树分治

视频链接：

P5787 二分图 /【模板】线段树分治 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 线段树分治 O(mlognlogk)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

#define mid ((l+r)>>1)
const int N=400005;
int n,m,k,p[N],high[N],top;
struct E{int x,y;}e[N]; //存边
struct stack{
  int x,y,add;    //高度相等则add=1,否则add=0
}st[N];           //用栈记录边的端点的合并信息
vector<int> t[N]; //在线段树节点上记录时间线

void insert(int u,int l,int r,int L,int R,int i){
  if(L>r||R<l) return;
  if(L<=l&&r<=R){
    t[u].push_back(i); //节点[l,r]上记录第i条时间线
    return;
  }
  insert(u<<1,l,mid,L,R,i);
  insert(u<<1|1,mid+1,r,L,R,i);
}
int find(int x){ //查找根
  while(x!=p[x]) x=p[x];
  return p[x];
}
void merge(int x,int y){ //合并集合
  x=find(x),y=find(y);
  if(high[x]>high[y]) swap(x,y);
  st[++top]={x,y,high[x]==high[y]}; //合并前的信息
  p[x]=y; //x指向y
  if(high[x]==high[y]) high[y]++; //y的高度+1
}
void solve(int u,int l,int r){ //线段树分治
  int flag=1; //1是二分图，0不是二分图
  int lasttop=top;
  //如果当前区间有时间线，若无环则合并，有环则输出
  for(int i=0;i<t[u].size();i++){
    if(find(e[t[u][i]].x)==find(e[t[u][i]].y)){
      for(int k=l;k<=r;k++) puts("No");
      flag=0; break;
    }
    merge(e[t[u][i]].x, e[t[u][i]].y+n);
    merge(e[t[u][i]].y, e[t[u][i]].x+n);
  }
  //如果当前区间存在二分图，则继续分治，直到叶子
  if(flag){
    if(l==r) puts("Yes"); //r时刻是二分图
    else{
      solve(u<<1,l,mid);
      solve(u<<1|1,mid+1,r); //继续分治
    }
  }
  //回溯，如果当前区间做过合并操作，则逐个撤销
  while(top>lasttop){ 
    high[p[st[top].x]]-=st[top].add;
    p[st[top].x]=st[top].x;
    top--;
  }
}
int main(){
  scanf("%d%d%d",&n,&m,&k);
  for(int i=1;i<=2*n;i++) p[i]=i,high[i]=1;
  for(int i=1,l,r;i<=m;i++){
    scanf("%d%d%d%d",&e[i].x,&e[i].y,&l,&r);
    insert(1,1,k,l+1,r,i); //插入时间线
  }
  solve(1,1,k); //线段树分治
}