【LOJ121】「离线可过」动态图连通性

题面

LOJ

题解

线段树分治的经典应用

可以发现每个边出现的时间是一个区间

而我们每个询问是一个点

所以我们将所有边的区间打到一颗线段树上面去

询问每个叶子用并查集维护节点的联通性就好了

注意并查集因为要撤消所以只能用按秩合并保证复杂度

具体实现详见代码

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = getchar();

    if (ch == '-') w = -1, ch = getchar();

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

    return w * data;

}

const int MAX_N = 5e3 + 5;

const int MAX_M = 5e5 + 5;

int N, M, tim[MAX_N][MAX_N];

vector<int> vec[MAX_M << 2];

struct Query { int x, y, t, id; } q[MAX_M], lq[MAX_M], rq[MAX_M];

struct Modify { int x, y; } p[MAX_M];

bool ans[MAX_M];

int fa[MAX_N], rnk[MAX_N];

pair<int, int> stk[MAX_N]; int top;

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

void unite(int x, int y) {

	x = getf(x), y = getf(y);

	if (x == y) return ;

	if (rnk[x] < rnk[y]) swap(x, y);

	fa[y] = x;

	stk[++top] = make_pair(y, rnk[y]);

	if (rnk[x] == rnk[y]) stk[++top] = make_pair(x, ++rnk[x]);

}

void Undo(int cur) {

	while (top > cur) {

		pair<int, int> pre = stk[top--];

		fa[pre.first] = pre.first;

		rnk[pre.first] = pre.second;

	}

}

#define lson (o << 1)

#define rson (o << 1 | 1)

void modify(int o, int l, int r, int ql, int qr, int pos) {

	if (ql <= l && r <= qr) return (void)vec[o].push_back(pos);

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

	if (ql <= mid) modify(lson, l, mid, ql, qr, pos);

	if (qr > mid) modify(rson, mid + 1, r, ql, qr, pos);

}

void Div(int o, int lval, int rval, int st, int ed) {

	if (st > ed) return ;

	int cur = top;

	for (int i = 0, l = vec[o].size(); i < l; i++) unite(p[vec[o][i]].x, p[vec[o][i]].y);

	if (lval == rval) {

		for (int i = st; i <= ed; i++)

	    	ans[q[i].id] = getf(q[i].x) == getf(q[i].y);

		return ;

	}

	int mid = (lval + rval) >> 1, lt = 0, rt = 0;

	for (int i = st; i <= ed; i++)

		if (q[i].t <= mid) lq[++lt] = q[i];

		else rq[++rt] = q[i];

	for (int i = 1; i <= lt; i++) q[st + i - 1] = lq[i];

	for (int i = 1; i <= rt; i++) q[st + i + lt - 1] = rq[i];

	Div(lson, lval, mid, st, st + lt - 1);

    Div(rson, mid + 1, rval, st + lt, ed);

	Undo(cur);

}

int cnt1, cnt2;

int main () {

	N = gi(), M = gi();

	for (int i = 1; i <= N; i++) fa[i] = i, rnk[i] = 1;

	for (int i = 1; i <= M; i++) {

		int op = gi(), x = gi(), y = gi();

	     if (x > y) swap(x, y);

		 if (op == 0) tim[x][y] = i;

		 if (op == 1) modify(1, 1, M, tim[x][y], i, ++cnt1), p[cnt1] = (Modify){x, y}, tim[x][y] = 0;

		 if (op == 2) q[++cnt2] = (Query){x, y, i, cnt2};

	}

	for (int i = 1; i <= N; i++)

		for (int j = i; j <= N; j++)

			if (tim[i][j]) modify(1, 1, M, tim[i][j], M, ++cnt1), p[cnt1] = (Modify){i, j};

	Div(1, 1, M, 1, cnt2);

	for (int i = 1; i <= cnt2; i++) ans[i] ? puts("Y") : puts("N");

	return 0;

}