\(\text{Solution}\)

线段树分治的模板

对时间分治，线段树下标表示时间

在线段树上处理每条覆盖当前区间的边，对当前的时间区间求答案

小区间的信息可以由大区间一路下来得到，那么答案就是叶子节点的答案

对于二分图的加边动态判定，可以用并查集维护

具体来说就是用带权并查集，维护每个点与其父亲点集的异同

因为线段树区间返回时需要撤销并查集操作，那么就打个可撤销并查集按秩合并即可

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#define re register

#define ls (p << 1)

#define rs (ls | 1)

using namespace std;

const int N = 2e5 + 5;

int n, m, k, tot, top;

struct node{

	int x, y;

	inline node(int u = 0, int v = 0){x = u, y = v;}

}e[N];

int Q[N << 2];

struct edge{

	int nxt, to;

	inline edge(int x = 0, int y = 0){nxt = x, to = y;}

}E[N * 21];

struct stack{

	int x, y;

	inline stack(int u = 0, int v = 0){x = u, y = v;}

}stk[N * 21];

inline void read(int &x)

{

	x = 0; char ch = getchar();

	while (!isdigit(ch)) ch = getchar();

	while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();

}

void update(int p, int l, int r, int tl, int tr, int x)

{

	if (tl <= l && r <= tr)

	{

		E[++tot] = edge(Q[p], x), Q[p] = tot;

		return;

	}

	int mid = (l + r) >> 1;

	if (tl <= mid) update(ls, l, mid, tl, tr, x);

	if (tr > mid) update(rs, mid + 1, r, tl, tr, x);

}

int fa[N], siz[N], d[N], ans[N];

int find(int x){return (fa[x] == x ? x : find(fa[x]));}

int getdis(int x)

{

	if (x == fa[x]) return d[x];

	return d[x] ^ getdis(fa[x]);

}

void solve(int p, int l, int r)

{

	int lst = top, flag = 0, mid = (l + r) >> 1;

	for(re int i = Q[p], x, y, u, v; i; i = E[i].nxt)

	{

		x = e[E[i].to].x, y = e[E[i].to].y, u = find(x), v = find(y);

		if (u ^ v)

		{

			if (siz[u] > siz[v]) swap(u, v), swap(x, y);

			fa[u] = fa[v], d[u] = d[x] ^ d[y] ^ 1, siz[v] += siz[u];

			stk[++top] = stack(u, v);

		}

		else if (!(getdis(x) ^ getdis(y))){flag = 1; break;}

	}

	if (flag ^ 1)

		if (l ^ r) solve(ls, l, mid), solve(rs, mid + 1, r);

		else ans[l] = 1;

	for(int x, y; lst ^ top; --top)

		x = stk[top].x, y = stk[top].y, fa[x] = x, d[x] = 0, siz[y] -= siz[x];

}

int main()

{

	read(n), read(m), read(k);

	for(re int i = 1, l, r, x, y; i <= m; i++)

		read(x), read(y), read(l), read(r), ++l, ++r, e[i] = node(x, y), update(1, 1, n, l, r - 1, i);

	for(re int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;

	solve(1, 1, k);

	for(re int i = 1; i <= k; i++) (ans[i] ? printf("Yes\n") : printf("No\n"));

}

巴特西

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

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章