题目

分析：

从前天早上肝到明天早上qwq其实颓了一上午MC ，自己瞎yy然后1A，写篇博客庆祝一下。

首先做这题之前推荐一道很相似的题：【BZOJ4025】二分图（可撤销并查集+线段树分治）

大力每个颜色维护一个并查集，就很像上面那道题了。但是存在一个问题：在处理线段树区间\([l,r]\)时，可能并不知道\(l\)处的修改是否成功，所以不知道\(l\)处修改的边具体是什么颜色的。

我的解决方案是：处理区间\([l,r]\)时忽略\(l\)处修改的边。先向左子树递归，递归到叶子时判断本次修改颜色能否成功。然后回溯后向右子树递归前将这条边加入。

代码：

solve函数的第四个参数表示现在是否已经忽略了\(l\)处修改的边。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <queue>

#include <bitset>

#include <stack>

using namespace std;

namespace zyt

{

	template<typename T>

	inline void read(T &x)

	{

		char c;

		bool f = false;

		x = 0;

		do

			c = getchar();

		while (c != '-' && !isdigit(c));

		if (c == '-')

			f = true, c = getchar();

		do

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

		while (isdigit(c));

		if (f)

			x = -x;

	}

	template<typename T>

	inline void write(T x)

	{

		static char buf[20];

		char *pos = buf;

		if (x < 0)

			putchar('-'), x = -x;

		do

			*pos++ = x % 10 + '0';

		while (x /= 10);

		while (pos > buf)

			putchar(*--pos);

	}

	inline void write(const char *const s)

	{

		printf("%s", s);

	}

	const int N = 5e5 + 10, B = 19, K = 51;

	int n, m, k, q, head[1 << (B + 1) | 11], ecnt;

	struct UFS

	{

		int fa[N], rk[N];

		bitset<N> dis;

		struct node

		{

			UFS &ufs;

			int x, y, fa, rk, dis;

		};

		static stack<node> sta;

		inline void init()

		{

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

				fa[i] = i, rk[i] = 1;

			dis = 0U;

		}

		int f(const int x)

		{

			return x == fa[x] ? x : f(fa[x]);

		}

		int dist(const int x)

		{

			return x == fa[x] ? dis[x] : dist(fa[x]) ^ dis[x];

		}

		inline bool merge(const int u, const int v)

		{

			int x = f(u), y = f(v);

			if (x == y)

				return dist(u) ^ dist(v);

			if (rk[x] > rk[y])

				swap(x, y);

			sta.push((node){*this, x, y, fa[x], rk[y], dis[x]});

			fa[x] = y, dis[x] = dis[x] ^ dist(u) ^ dist(v) ^ 1;

			if (rk[x] == rk[y])

				++rk[y];

			return true;

		}

		static inline int set_undo()

		{

			return sta.size();

		}

		static inline void undo(const int bck)

		{

			while (sta.size() > bck)

			{

				UFS &now = sta.top().ufs;

				now.fa[sta.top().x] = sta.top().fa;

				now.rk[sta.top().y] = sta.top().rk;

				now.dis[sta.top().x] = sta.top().dis;

				sta.pop();

			}

		}

	}ufs[K];

	stack<UFS::node> UFS::sta;

	struct edge

	{

		int id, next;

	}e[N * B];

	inline void add(const int a, const int b)

	{

		e[ecnt] = (edge){b, head[a]}, head[a] = ecnt++;

	}

	struct ed

	{

		int u, v;

	}arr[N];

	struct node

	{

		int ed, col;

	}mdf[N];

	int pre[N], nxt[N], last[N];

	namespace Segment_Tree

	{

		void insert(const int rot, const int lt, const int rt, const int ls, const int rs, const int id)

		{

			if (ls <= lt && rt <= rs)

			{

				add(rot, id);

				return;

			}

			int mid = (lt + rt) >> 1;

			if (ls <= mid)

				insert(rot << 1, lt, mid, ls, rs, id);

			if (rs > mid)

				insert(rot << 1 | 1, mid + 1, rt, ls, rs, id);

		}

		void solve(const int rot, const int lt, const int rt, bool flag)

		{

			int mid = (lt + rt) >> 1;

			int bck = UFS::set_undo();

			bool f = false;

			for (int i = head[rot]; ~i; i = e[i].next)

			{

				int now = e[i].id;

				if (lt == now)

				{

					flag = true;

					continue;

				}

				UFS &u = ufs[mdf[now].col];

				ed &edg = arr[mdf[now].ed];

				if (mdf[now].col)

					u.merge(edg.u, edg.v);

			}

			if (lt == rt)

			{

				if (!ufs[mdf[lt].col].merge(arr[mdf[lt].ed].u, arr[mdf[lt].ed].v))

					mdf[lt].col = mdf[pre[lt]].col, write("NO");

				else

					write("YES");

				putchar('\n');

			}

			else

			{

				solve(rot << 1, lt, mid, f | flag);

				if (f | flag)

					ufs[mdf[lt].col].merge(arr[mdf[lt].ed].u, arr[mdf[lt].ed].v);

				solve(rot << 1 | 1, mid + 1, rt, false);

			}

			UFS::undo(bck);

		}

	}

	int work()

	{

		using namespace Segment_Tree;

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

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

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

			ufs[i].init();

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

			read(arr[i].u), read(arr[i].v);

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

		{

			read(mdf[i].ed), read(mdf[i].col);

			nxt[i] = q + 1;

		}

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

		{

			if (last[mdf[i].ed])

				pre[i] = last[mdf[i].ed];

			last[mdf[i].ed] = i;

		}

		for (int i = q; i > 0; i--)

			nxt[pre[i]] = i;

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

			insert(1, 1, q, i, nxt[i] - 1, i);

		solve(1, 1, q, false);

		return 0;

	}

}

int main()

{

	return zyt::work();

}

巴特西

【Codeforces576E_CF576E】Painting Edges（可撤销并查集+线段树分治）

题目

分析：

代码：

最新文章

热门文章