BZOJ3674 可持久化并査集

@(BZOJ)[可持久化并査集]

Description

n个集合 m个操作

操作：

1 a b 合并a,b所在集合

2 k 回到第k次操作之后的状态(查询算作操作)

3 a b 询问a,b是否属于同一集合，是则输出1否则输出0

请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为0

0<n,m<=2*10^5

Sample Input

Sample Output

Solution

模板题.

BZOJ上的数据傻到不行.

还是去xsy上提交吧

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

const int N = 1 << 18, M = 1 << 18;

int n;

namespace Zeonfai

{

	inline int getInt()

	{

		int a = 0, sgn = 1;

		char c;

		while(! isdigit(c = getchar()))

			sgn *= c == '-' ? -1 : 1;

		while(isdigit(c))

			a = a * 10 + c - '0', c = getchar();

		return a * sgn;

	}

}

struct persistentDisjointSet

{

	int rt[M], tp;

	struct data

	{

		int pre, dep;

	};

	struct node

	{

		int suc[2];

		data infr;

	}nd[N * 18 + M * 18];

	inline int newNode(int pre, int dep)

	{

		nd[tp].suc[0] = nd[tp].suc[1] = -1;

		nd[tp].infr.pre = pre, nd[tp].infr.dep = dep;

		return tp ++;

	}

	int build(int L, int R)

	{

		int u = newNode(L == R ? L : -1, 1);

		if(L == R)

			return u;

		int mid = L + R >> 1;

		nd[u].suc[0] = build(L, mid), nd[u].suc[1] = build(mid + 1, R);

		return u;

	}

	inline void initialize()

	{

		memset(rt, -1, sizeof(rt));

		tp = 0;

		rt[0] = build(1, n);

	}

	int find(int L, int R, int u, int a)

	{

		if(L == R)

			return u;

		int mid = L + R >> 1;

		if(a <= mid)

			return find(L, mid, nd[u].suc[0], a);

		else

			return find(mid + 1, R, nd[u].suc[1], a);

	}

	inline int access(int tm, int a)

	{

		while(int u = find(1, n, rt[tm], a))

		{

			if(nd[u].infr.pre == a)

				return a;

			a = nd[u].infr.pre;

		}

	}

	int newSegmentTree(int _u, int L, int R, int a, int b)

	{

		int u = tp ++;

		nd[u] = nd[_u];

		if(L == R)

			return u;

		int mid = L + R >> 1;

		if((a >= L && a <= mid) || (b >= L && b <= mid))

			nd[u].suc[0] = newSegmentTree(nd[_u].suc[0], L, mid, a, b);

		if((a > mid && a <= R) || (b > mid && b <= R))

			nd[u].suc[1] = newSegmentTree(nd[_u].suc[1], mid + 1, R, a, b);

		return u;

	}

	inline void merge(int tm, int a, int b)

	{

		int rtA = access(tm - 1, a), rtB = access(tm - 1, b);

		if(rtA == rtB)

		{

			rt[tm] = rt[tm - 1];

			return;

		}

		rt[tm] = newSegmentTree(rt[tm - 1], 1, n, rtA, rtB);

		int u = find(1, n, rt[tm], rtA), v = find(1, n, rt[tm], rtB);

		if(nd[u].infr.dep == nd[v].infr.dep)

		{

			++ nd[u].infr.dep;

			nd[v].infr.pre = rtA;

			return;

		}

		if(nd[u].infr.dep > nd[v].infr.dep)

			nd[v].infr.pre = rtA;

		else

			nd[u].infr.pre = rtB;

	}

	inline void accessHistory(int tm, int _tm)

	{

		rt[tm] = rt[_tm];

	}

	inline int query(int tm, int a, int b)

	{

		rt[tm] = rt[tm - 1];

		int preA = access(tm, a), preB = access(tm, b);

		if(preA == preB)

			return 1;

		else

			return 0;

	}

}st;

int main()

{

	#ifndef ONLINE_JUDGE

	freopen("BZOJ3674.in", "r", stdin);

	freopen("BZOJ3674.out", "w", stdout);

	#endif

	using namespace Zeonfai;

	n = getInt();

	int m = getInt(), lstAns = 0, tm = 0;

	st.initialize();

	while(m --)

	{

		int opt = getInt();

		if(opt == 1)

		{

			int a = getInt() ^ lstAns, b = getInt() ^lstAns;

			st.merge(++ tm, a, b);

		}

		else if(opt == 2)

		{

			int a = getInt() ^ lstAns;

			st.accessHistory(++ tm, a);

		}

		else if(opt == 3)

		{

			int a = getInt() ^ lstAns, b = getInt() ^ lstAns;

			printf("%d\n", lstAns = st.query(++ tm, a, b));

		}

	}

}

巴特西

BZOJ3674 可持久化并査集

Description

Sample Input

Sample Output

Solution

最新文章

热门文章