题目：

分析：

很明显，查询的是删掉某条边后两端点所在连通块大小的乘积。

有加边和删边，想到LCT。但是我不会用LCT查连通块大小啊。果断弃了

有加边和删边，还跟连通性有关，于是开始yy线段树分治做法（不知道线段树分治？推荐一个伪模板题BZOJ4025二分图事实上这个链接是指向我的博客的）。把每次操作（加边或查询）看做一个时刻，一条边存在的区间就是它加入后没有被查询的时间区间的并。于是用可撤销并查集维护一下连通块大小即可。

代码：

#include <cstdio>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <map>

#include <cassert>

#undef i

#undef j

#undef k

#undef min

#undef max

#undef true

#undef false

#undef swap

#undef sort

#undef if

#undef for

#undef while

#undef printf

#undef scanf

#undef putchar

#undef getchar

#define _ 0

using namespace std;

namespace zyt

{

	template<typename T>

	inline bool read(T &x)

	{

		char c;

		bool f = false;

		x = 0;

		do

			c = getchar();

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

		if (c == EOF)

			return false;

		if (c == '-')

			f = true, c = getchar();

		do

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

		while (isdigit(c));

		if (f)

			x = -x;

		return true;

	}

	inline bool read(char &c)

	{

		do

			c = getchar();

		while (c != EOF && !isgraph(c));

		return c != EOF;

	}

	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);

	}

	typedef long long ll;

	const int N = 1e5 + 10, B = 17, QUERY = 0, ADD = 1;

	int n, q;

	ll ans[N];

	struct node

	{

		bool type;

		int x, y;

	}arr[N];

	namespace UFS

	{

		int fa[N], rk[N], size[N], top;

		struct node

		{

			int x, y, fax, rky, sizey;

		}stack[N];

		void init(const int n)

		{

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

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

		}

		int f(const int u)

		{

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

		}

		bool merge(const int u, const int v)

		{

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

			if (x == y)

				return false;

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

				swap(x, y);

			stack[top++] = (node){x, y, fa[x], rk[y], size[y]};

			fa[x] = y, size[y] += size[x];

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

				++rk[y];

			return true;

		}

		int query(const int u)

		{

			assert(f(u) < N);

			return size[f(u)];

		}

		void undo(const int bck)

		{

			while (top > bck)

			{

				--top;

				int x = stack[top].x, y = stack[top].y;

				assert(x < N && y < N);

				fa[x] = stack[top].fax;

				rk[y] = stack[top].rky;

				size[y] = stack[top].sizey;

			}

		}

	}

	namespace Segment_Tree

	{

		struct edge

		{

			int x, y, next;

		}e[N * (B + 1)];

		int head[1 << (B + 1) | 11], ecnt;

		inline void init()

		{

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

		}

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

		{

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

		}

		inline void insert(const int rot, const int lt, const int rt, const int ls, const int rs, const int x, const int y)

		{

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

			{

				add(rot, x, y);

				return;

			}

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

			if (ls <= mid)

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

			if (rs > mid)

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

		}

		inline void solve(const int rot, const int lt, const int rt)

		{

			int bck = UFS::top;

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

				UFS::merge(e[i].x, e[i].y);

			if (lt == rt)

			{

				if (arr[lt].type == QUERY)

					ans[lt] = (ll)UFS::query(arr[lt].x) * UFS::query(arr[lt].y);

				UFS::undo(bck);

				return;

			}

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

			solve(rot << 1, lt, mid);

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

			UFS::undo(bck);

		}

	}

	map<pair<int, int>, int> lastins;

	int work()

	{

		read(n), read(q);

		UFS::init(n);

		Segment_Tree::init();

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

		{

			char opt;

			read(opt), read(arr[i].x), read(arr[i].y);

			if (arr[i].x > arr[i].y)

				swap(arr[i].x, arr[i].y);

			arr[i].type = (opt == 'Q' ? QUERY : ADD);

			pair<int, int> p = make_pair(arr[i].x, arr[i].y);

			if (arr[i].type == ADD)

				lastins[p] = i;

			else

			{

				Segment_Tree::insert(1, 1, q, lastins[p], i - 1, p.first, p.second);

				lastins[p] = i + 1;

			}

		}

		for (map<pair<int, int>, int>::iterator it = lastins.begin(); it != lastins.end(); it++)

			if (it->second <= q)

				Segment_Tree::insert(1, 1, q, it->second, q, it->first.first, it->first.second);

		Segment_Tree::solve(1, 1, q);

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

			if (arr[i].type == QUERY)

				write(ans[i]), putchar('\n');

		return (0^_^0);

	}

}

int main()

{

	return zyt::work();

}

巴特西

【洛谷4219】[BJOI2014]大融合（线段树分治）

题目：

分析：

代码：

最新文章

热门文章