Solution
- 以时间 \([0..T]\) 为下标建一棵线段树
- 线段树上的每个区间维护一个边集
- 对于一条边 \(i\)，它存在的时间区间为： \([start_i,end_i-1]\)
- 把 \([start_i,end_i-1]\) 区间拆成线段树上的 \(O(\log T)\) 个区间
- 并且把边 \(i\) 丢进这些区间的边集
- 然后把整棵线段树 \(dfs\) 一遍
- \(dfs\) 到区间 \([l,r]\) 时，并查集维护的就是 \([l,r]\) 这段时间都存在的边，所组成的二分图
- 如果把二分图黑白染色，那么要保证同一个连通块中，同色的点处于同一并查集
- 由于距离最近的两个同色点通过异色点间接相连
- 把每个点 \(x\) 拆成 \(x\) 和 \(x+n\)
- 合并 \(x,y\) 即合并 \((x,y+n)\),\((y,x+n)\)
- 如果合并 \(x,y\) 时发现 \(x,y\) 已经处于同一连通块，那么它就不是二分图
- 具体地，记过程 \(dfs(l,r,p,opt)\) 表示 \(dfs\) 到区间 \([l,r]\)，此区间编号为 \(p\)，\(opt\)表示在加入 \(p\) 的边集之前，是不是二分图
- 初始时 \(opt=1\)
- \(dfs\) 到 \([l,r]\) 时，把 \(p\) 的边集加到并查集里去，加边过程中如果发现不是二分图了，就把 \(opt=0\)
- 然后 \(dfs(l,mid,lson[p],opt),dfs(mid + 1,r,rson[p],opt)\)
- \(dfs\) 到叶子的时候，就可以根据 \(opt\)，得到时刻 \(l\) 的答案了
- 回溯时要清掉 \(p\) 的边集
- 所以要用可持久化并查集，即不能路径压缩
- 为了保证时间复杂度采用启发式合并，即每次把 \(sze\)（或\(dep\)） 小的合并到大的
Code
#include <bits/stdc++.h>
using namespace std;
#define p2 p << 1
#define p3 p << 1 | 1
template <class t>
inline void read(t & res)
{
char ch;
while (ch = getchar(), !isdigit(ch));
res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + (ch ^ 48);
}
const int e = 2e6 + 5;
struct point
{
int x, y;
}a[e];
vector<int>g[e];
int stk[e], top, n, m, q, f[e], sze[e];
bool ans[e], pd;
inline int find(int x)
{
return !f[x] ? x : find(f[x]);
}
inline void merge(int x, int y)
{
stk[++top] = 0;
x = find(x);
y = find(y);
if (x == y) return;
if (sze[x] > sze[y]) swap(x, y);
sze[y] += sze[x];
f[x] = y;
stk[top] = x;
}
inline void del()
{
int x = stk[top--];
if (!x) return;
sze[f[x]] -= sze[x];
f[x] = 0;
}
inline void modify(int l, int r, int s, int t, int v, int p)
{
if (l == s && r == t)
{
g[p].push_back(v);
return;
}
int mid = l + r >> 1;
if (t <= mid) modify(l, mid, s, t, v, p2);
else if (s > mid) modify(mid + 1, r, s, t, v, p3);
else
{
modify(l, mid, s, mid, v, p2);
modify(mid + 1, r, mid + 1, t, v, p3);
}
}
inline void dfs(int l, int r, int p, int opt)
{
int i, len = g[p].size();
for (i = 0; i < len; i++)
{
int j = g[p][i];
int x = a[j].x, y = a[j].y;
if (find(x) == find(y)) opt = 0;
merge(x, y + n);
merge(x + n, y);
}
if (l == r)
{
ans[l] = opt;
for (i = 0; i < len; i++)
{
del();
del();
}
return;
}
int mid = l + r >> 1;
dfs(mid + 1, r, p3, opt);
dfs(l, mid, p2, opt);
for (i = 0; i < len; i++)
{
del();
del();
}
}
int main()
{
read(n); read(m); read(q);
int i, l, r;
for (i = 1; i <= 2 * n; i++) sze[i] = 1;
for (i = 1; i <= m; i++)
{
read(a[i].x);
read(a[i].y);
read(l);
read(r);
r--;
if (l <= r) modify(0, q, l, r, i, 1);
}
dfs(0, q, 1, 1);
for (i = 0; i < q; i++) puts(ans[i] ? "Yes" : "No");
return 0;
}