P5787

发表于 分类于
二分图 /【模板】线段树分治

二分图 /【模板】线段树分治

这里要用可撤销扩展域并查集。。。

扩展域并查集就是拆点表示关系，我们把一个点拆成两个点 $x_1$ 和 $x_2$，分别表示命题 $x$ 在 1 集合中和 $x$ 在 2 集合中。然后 $x$ 与 $y$ 连边相当于 $x_1\Leftrightarrow y_2$ 和 $x_2\Leftrightarrow y_1$，分别用并查集合并即可。遇到矛盾的情况比如 $x_1$ 与 $y_1$ 在同一集合中说明不是二分图。

然后主要就是可撤销并查集这个东西。

我们用一个栈来存储操作前的值，然后每次撤销的时候用这个值一步一步还原本来的并查集即可。

因为要求可撤销，一般的路径压缩可能会比较麻烦（比较 nb 的话是不是可以把路径压缩的操作一并撤销啊/yiw，感觉上复杂度似乎有些正确但我不会写啊 QAQ）。

所以我们用按秩合并，把深度小的接到深度大的下面。复杂度我不会证啊 QAQ，应该是 $O(\log n)$ 的吧。

当然如果你觉得可撤销并查集太 Trivial，你可以试试 LCT 实现可撤销并查集，不过听上去就 not practical。

然后会了可撤销并查集，线段树分治的操作实际上很好理解啊。

把一段时间 $[l,r]$ 内的操作覆盖到线段树上，因为操作比较多，每个线段树上的节点可以用一个 vector 来存储这个时间段内的所有操作。

然后我们从线段树的左侧向右侧遍历即可，实际就是一 Dfs，然后用并查集检查一下，如果不是二分图，这个节点代表的整个区间都不是二分图，全部输出 No。反之我们往下继续搜，搜到叶子结点如果还是二分图说明就是了，输出 Yes。最后再把操作都撤销掉即可。

时间复杂度 $O(m\log k\log n)$。

我解释一下这个复杂度，对于 $m$ 个操作，每个操作摊成线段树上的 $O(\log k)$ 个操作，每个操作对应 $O(1)$ 次并查集，一次并查集 $O(\log n)$，乘起来就完了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=1e6;

ll n,m,k,top;
ll fa[N+5],d[N+5];

struct Qry{ll l,r,u,v;}q[N+5];

struct Opt{
  ll x,val;
  inline Opt() {};
  inline Opt(ll a,ll b):x(a),val(b) {}
}st[N+5];

struct Edge{
  ll u,v;
  inline Edge() {}
  inline Edge(ll a,ll b):u(a),v(b) {}
};
vector<Edge> e[N+5];

inline void Add(ll p,ll lp,ll rp,ll l,ll r,ll u,ll v) {
  if(lp>=l&&rp<=r) {e[p].push_back(Edge(u,v));return;}
  ll mid=(lp+rp)>>1;
  if(l<=mid) Add(p<<1,lp,mid,l,r,u,v);
  if(r>mid) Add(p<<1|1,mid+1,rp,l,r,u,v);
}

inline void Revo() {
  ll x=st[top].x,val=st[top].val;d[fa[x]]=val;fa[x]=x;top--;
}

inline ll Get(ll x) {
  if(x==fa[x]) return x;d[fa[x]]=max(d[fa[x]],d[x]+1);return Get(fa[x]);
}

inline void Merge(ll x,ll y) {
  ll u=Get(x),v=Get(y);if(d[u]<d[v]) swap(u,v);
  st[++top]=Opt(v,d[u]);fa[v]=u;d[u]=max(d[v]+1,d[u]);
}

inline void Dfs(ll p,ll lp,ll rp) {
  ll flg=0,pos=top;
  for(ll i=0;i<(ll)e[p].size();i++) {
    ll a=e[p][i].u,b=e[p][i].v;
    if(Get(a)==Get(b)) {flg=i+1;break;}
    Merge(a,b+n);Merge(a+n,b);
  }
  if(flg) {for(ll i=lp;i<=rp;i++) {printf("No\n");}}
  else {
    if(lp==rp) {printf("Yes\n");}
    else {ll mid=(lp+rp)>>1;Dfs(p<<1,lp,mid);Dfs(p<<1|1,mid+1,rp);}
  }
  while(top>pos) {ll x=st[top].x;d[fa[x]]=st[top].val;fa[x]=x;top--;}
}

int main() {

  n=read();m=read();k=read();
  for(ll i=1;i<=2*n;i++) fa[i]=i;

  for(ll i=1;i<=m;i++) {
    q[i].u=read();q[i].v=read();q[i].l=read();q[i].r=read();
    Add(1,1,k,q[i].l+1,q[i].r,q[i].u,q[i].v);
  }

  Dfs(1,1,k);

  return 0;
}