BZOJ4025 二分图

【题目描述】

神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。

【输入】

输入数据的第一行是三个整数n,m,T。

第2行到第m+1行，每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点，这条边在start时刻出现，在第end时刻消失。

【输出】

输出包含T行。在第i行中，如果第i时间段内这个图是二分图，那么输出“Yes”，否则输出“No”，不含引号。

【输入样例】

【输出样例】

Yes
No
Yes

【提示】

样例说明：

0时刻，出现两条边1-2和2-3。

第1时间段内，这个图是二分图，输出Yes。

1时刻，出现一条边1-3。

第2时间段内，这个图不是二分图，输出No。

2时刻，1-2和1-3两条边消失。

第3时间段内，只有一条边2-3，这个图是二分图，输出Yes。

数据范围：

n≤100000，m≤200000，T≤100000，1≤u,v≤n，0≤start≤end≤T。

本题虽然可以用LCT做，但也可以用一种十分特殊的分治技巧。

我们考虑在时间轴上做分治。对于一条边，我们考虑在时间区间插入这条边。对于区间插入我们可以考虑模仿线段树的做法——对时间轴建立线段树，类似标记永久化的，把一条边出现的时段分配到线段树上log个区间，在线段树上进行区间修改操作。等到把所有的边都分配好之后我们dfs整个线段树，用并查集维护环的奇偶性，每到一个节点把该节点所有的边插入并查集，每出一个节点撤销该节点进行的所有操作即可。（具体做法见代码）

其实实现起来的话我们可以一边分区间一边dfs——每到一层遍历当前时间区间分到的所有的边，把左右区间恰好为当前管辖区间的边插入并查集，把其他操作用线段树的做法递归到左边和右边（分r <= mid, l > mid, l <=mid < r三种情况），这一步可以新开一个vector，把vector数组下标分配下去。这样我们写一个带撤销的并查集就好了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 2e5 + 5;

namespace DSU {
	stack<int > stk;
	stack<int > dstk;
	int fa[maxn], dis[maxn], siz[maxn], tmp;
	void init(int n) {For(i, 1, n) fa[i] = i, siz[i] = 1;}
	int find(int x) {return fa[x] == x ? x : find(fa[x]);}
	int Gdis(int x) {return fa[x] == x ? 0 : dis[x] ^ Gdis(fa[x]);}
	bool combine(int x, int y) {
		int w = Gdis(x) ^ Gdis(y) ^ 1;
		x = find(x), y = find(y);
		if(x == y) return false;
		if(siz[y] > siz[x]) swap(x, y); 
		dstk.push(dis[y]), dis[y] = w, fa[y] = x;
		stk.push(y), siz[x] += siz[y];
		return true;
	}
	void remove() {
		tmp = stk.top();
		dis[tmp] = dstk.top();
		siz[fa[tmp]] -= siz[tmp];
		fa[tmp] = tmp, stk.pop(), dstk.pop();
	}
	void back(int x) {while(x--) remove();}
}

int cnt, ans[maxn], n, m, t;
struct OPR {
	int u, v, l, r;
	OPR CH(int a, int b) {return (OPR) {u, v, a, b};}
}npr;
vector<OPR > NP[maxn << 1];
void cdq(int l, int r, int now) {
	int mid = l + r >> 1, CL = ++cnt, CR = ++cnt, oprs = 0;
	if(l == r) {
		for(register int i = NP[now].size() - 1; i >= 0; --i) {
			npr = NP[now][i];
			if(DSU::combine(npr.u, npr.v)) ++oprs; else
			if(DSU::Gdis(npr.u) ^ DSU::Gdis(npr.v) ^ 1)
				return DSU::back(oprs), ans[l] = -1, void();
		}
		return DSU::back(oprs), ans[l] = 1, void();
	}
	for(register int i = NP[now].size() - 1; i >= 0; --i) {
		npr = NP[now][i];
		if(npr.l == l && npr.r == r) {
			if(DSU::combine(npr.u, npr.v)) ++oprs; else
			if(DSU::Gdis(npr.u) ^ DSU::Gdis(npr.v) ^ 1) {
				For(j, l, r) ans[j] = -1;
				return DSU::back(oprs), void();
			}
		} else {
			if(npr.r <= mid) NP[CL].push_back(npr);
			else if(npr.l > mid) NP[CR].push_back(npr);
			else {
				NP[CL].push_back(npr.CH(npr.l, mid));
				NP[CR].push_back(npr.CH(mid + 1, npr.r));
			}
		}
	}
	cdq(l, mid, CL), cdq(mid + 1, r, CR);
	DSU::back(oprs);
}

int main() {
	scanf("%d%d%d", &n, &m, &t), DSU::init(n);
	For(i, 1, m) {
		scanf("%d%d%d%d", &npr.u, &npr.v, &npr.l, &npr.r);
		--npr.r, NP[cnt].push_back(npr);
	}
	cdq(0, t, 0);
	For(i, 0, t - 1) printf("%s\n", ans[i] > 0 ? "Yes" : "No");
	return 0;
}

Rockdu's Blog