「HNOI2016」最小公倍数 - 分块 + 可撤销带权并查集

给定一张 $N$ 个顶点 $M$ 条边的带边权无向图，所有权值都可以分解成 $2^a \cdot 3^b$的形式

现在有 $q$ 个询问，每次询问给定四个参数 和 $b$，请你求出是否存在一条顶点 $u$ 到 $v$ 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 $2^a \cdot 3^b$

注意：路径可以不是简单路径。

$n,q\le 5*10^4, m\le 10^5$

Links

LOJ 2048

Luogu P3247

Solution

发现就是询问是否存在一个$u\to v$的路径,满足$max\{a\}=A,max\{b\}=B$

对于这种双关键字都要满足限制的问题，我们通常可以考虑分块

注：以下内容中，按$(x,y)$排序是指以$x$为第一关键字，$y$为第二关键字排序

首先把边按$(a, b)$排序，并分成$k$块

从小到大枚举$k$个块，每次处理$a$在当前块$a$的范围内的询问

把当前需要处理的询问和前$k-1$个块的操作按$b$排序，依次进行操作。

具体地，我们使用可撤销带权并查集维护，在处理每个询问之前，暴力把当前块内满足条件的边连上，询问完再撤销

实现上的一些细节：

• 首先对询问按$(b,a)$排序，这样每次取出来的询问就是$b$这一维有序的了，于是就能用two pointer直接扫
• 有可能一些$a$相同的边被拆散到多个块内，如果直接判断$a\in [L[i].a, R[i].a]$的话就可能会导致同一个询问被处理多次。所以应该判断$a\in [L[i].a, R[i].a + 1)$，这样就保证了每个询问只会在最后一个相同$a$所属的块内被处理

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 50000 + 100, Maxm = 100000 + 100;

int N, M, Q;

struct info
{
	int x, y, a, b, id;
} E[Maxm], Query[Maxn];

int Ans[Maxn];

namespace DSU
{
	int fa[Maxn], size[Maxn], top;
	int val_a[Maxn], val_b[Maxn];
	info Stack[Maxm << 1];

	inline void init (int maxn) { top = 0; for (int i = 1; i <= maxn; ++i) fa[i] = i, size[i] = 1, val_a[i] = val_b[i] = -1; }

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

	inline void link (info now, int flag) 
	{ 
		int x = get_fa(now.x), y = get_fa(now.y); 
		if (size[x] < size[y]) swap(x, y);

		if (flag) Stack[++top] = (info){x, y, val_a[x], val_b[x], size[x]}; 

		if (x == y)
		{
			Chkmax (val_a[x], now.a);
			Chkmax (val_b[x], now.b);
			return ;
		}

		Chkmax (val_a[x], max(now.a, val_a[y]));
		Chkmax (val_b[x], max(now.b, val_b[y]));
		fa[y] = x;
		size[x] += size[y];
	}

	inline int check (info now)
	{
		int x = get_fa(now.x), y = get_fa(now.y);
		return (x == y) && (val_a[x] == now.a) && (val_b[x] == now.b);
	}

	inline void pop ()
	{
		while (top)
		{
			info now = Stack[top--];
			fa[now.y] = now.y;
			size[now.x] = now.id;
			val_a[now.x] = now.a;
			val_b[now.x] = now.b;
		}
	}
}

inline int cmp (info u, info v)
{
	if (u.a == v.a)
	{
		if (u.b == v.b) return u.id < v.id;
		return u.b < v.b;
	}
	return u.a < v.a;
}

inline int cmp2 (info u, info v)
{
	if (u.b == v.b)
	{
		if (u.a == v.a) return u.id < v.id;
		return u.a < v.a;
	}
	return u.b < v.b;
}

namespace BLOCK
{
	int block_size, block_cnt, L[Maxm], R[Maxm], Belong[Maxm];

	inline void init ()
	{
		sort (E + 1, E + M + 1, cmp);
		block_size = sqrt(M * log(M)), block_cnt = (M - 1) / block_size + 1;
		//cout << block_size << ' ' << block_cnt << endl;

		for (int i = 1; i <= block_cnt; ++i)
			L[i] = R[i - 1] + 1, R[i] = min(M, L[i] + block_size - 1);
		for (int i = 1; i <= M; ++i) Belong[i] = (i - 1) / block_size + 1;
	}

	info Now[Maxn];

	inline void solve ()
	{
		sort (Query + 1, Query + Q + 1, cmp2);

		for (int i = 1; i <= block_cnt; ++i)
		{
			DSU :: init (N);
			int cnt = 0;
			for (int j = 1; j <= Q; ++j)
/**/			if (E[L[i]].a <= Query[j].a && Query[j].a < E[R[i] + 1].a)
					Now[++cnt] = Query[j];

			sort (E + 1, E + L[i], cmp2);

			int pos = 1;
			for (int j = 1; j <= cnt; ++j)
			{
				while (pos < L[i] && E[pos].b <= Now[j].b) DSU :: link (E[pos++], 0);

				for (int k = L[i]; k <= R[i]; ++k)
					if (E[k].b <= Now[j].b && E[k].a <= Now[j].a)
						DSU :: link (E[k], 1);

				Ans[Now[j].id] = DSU :: check (Now[j]);
				DSU :: pop ();
			}
		}
	}
}

inline void Solve ()
{
	BLOCK :: init ();
	BLOCK :: solve ();

	for (int i = 1; i <= Q; ++i) printf("%s\n", Ans[i] ? "Yes" : "No");

#ifdef hk_cnyali
	cerr << (double)clock() / CLOCKS_PER_SEC << endl;
#endif
}

inline void Input ()
{
	N = read<int>(), M = read<int>();

	for (int i = 1; i <= M; ++i)
	{
		int x = read<int>(), y = read<int>(), a = read<int>(), b = read<int>();
		E[i] = (info){x, y, a, b, i};
	}
	E[M + 1] = (info){0, 0, (int)2e9, (int)2e9, 0};

	Q = read<int>();

	for (int i = 1; i <= Q; ++i)
	{
		int x = read<int>(), y = read<int>(), a = read<int>(), b = read<int>();
		Query[i] = (info){x, y, a, b, i};
	}
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}

Debug

• 137L： 写成Query[i].a <= E[R[i]].a