「HNOI2016」最小公倍数（回滚莫队，并查集）

题目链接

LOJ

洛谷

题意简述

给你一张带边权的无向图，边权都形如 $2^a3^b$ ，若干询问，每次问是否存在 $u$ 到 $v$ 且边权的最小公倍数为 $2^a3^b$ 的途径（可以不是简单路径）。

点数 $5\cdot 10^4$，边数 $10^5$，询问数 $5\cdot 10^4$ 。

简要做法

首先转化问题：仅保留图中 $2$ 的指数不超过 $a$ 且 $3$ 的指数不超过 $b$ 的边，是否满足“$u$ 和 $v$ 连通，且连通块内 $2$ 的最高指数为 $a$，$3$ 的最高指数为 $b$”？

发现 $a$ 和 $b$ 在增大/减小时会导致边加入图中/从图中删去，这和莫队的左右指针很像。事实上这题的确可以看作一种长得比较奇怪的莫队。

具体来说，维护 $a$ 指针和 $b$ 指针，由于每条边要么先被 $a$ 指针扫到，要么先被 $b$ 指针扫到，增大其中一个指针时判一下是否满足另一个指针的要求，若满足则加入图中即可。

由于删边不好维护，可以使用类似 回滚莫队 的方法处理，但由于本题的特殊性，不存在“左右端点在同一块的暴力计算”这种情况。

具体实现可以参考代码（

坑

形如 u u 0 0 的询问若不存在 $(u, v)$ 的边权为 $1$ 则答案为 No，所以连通块内 $2$ 和 $3$ 指数的初值要赋为 $-1$ 。

个人觉得 u u 0 0 答案不为 Yes 很蠢..

参考代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

int B;

struct Edge
{
	int u, v, a, b;
	Edge(int _a = 0, int _b = 0): a(_a), b(_b) {}
};

vector<Edge> a, b;

struct Query
{
	int u, v, a, b, ra, rb, id;
	Query(int _u, int _v, int _a, int _b, int _ra, int _rb, int _id):
		u(_u), v(_v), a(_a), b(_b), ra(_ra), rb(_rb), id(_id) {}
	bool operator<(const Query& y) const
	{
		return b < y.b;
	}
};

vector<vector<Query> > q;

int n, m, k, qa, qb;
vector<bool> ans;

struct UnionFindSet
{
	int tim;
	vector<int> f, siz, two, three;
	
	struct Change
	{
		int x, y, x2, x3;
		Change(int _x, int _y, int _x2, int _x3): x(_x), y(_y), x2(_x2), x3(_x3) {}
	};
	
	stack<Change> c;
	
	int find(int x)
	{
		return x == f[x] ? x : find(f[x]);
	}
	
	void merge(int x, int y, int tw, int th)
	{
		x = find(x);
		y = find(y);
		if (x == y)
		{
			c.emplace(x, -1, two[x], three[x]);
			two[x] = max(two[x], tw);
			three[x] = max(three[x], th);
			return;
		}
		if (siz[x] < siz[y]) swap(x, y);
		c.emplace(x, y, two[x], three[x]);
		siz[x] += siz[y];
		f[y] = x;
		two[x] = max(tw, max(two[x], two[y]));
		three[x] = max(th, max(three[x], three[y]));
	}
	
	void record() { tim = c.size(); }
	
	void rollback()
	{
		while (c.size() > tim)
		{
			auto t = c.top();
			c.pop();
			if (~t.y)
			{
				f[t.y] = t.y;
				siz[t.x] -= siz[t.y];
				two[t.x] = t.x2;
				three[t.x] = t.x3;
			}
			else
			{
				two[t.x] = t.x2;
				three[t.x] = t.x3;
			}
		}
	}
	
	void reset()
	{
		f.resize(n + 1);
		siz.assign(n + 1, 1);
		two.assign(n + 1, -1);
		three = two;
		for (int i = 1; i <= n; ++i) f[i] = i;
		tim = 0;
		while (!c.empty()) c.pop();
	}
	
	void check(Query t)
	{
		int u = find(t.u);
		int v = find(t.v);
		ans[t.id] = u == v && two[u] == t.ra && three[u] == t.rb;
	}
} ufs;

bool cmpa(const Edge& x, const Edge& y)
{
	return x.a < y.a;
}

bool cmpb(const Edge& x, const Edge& y)
{
	return x.b < y.b;
}

void adda(int x)
{
	if (~qb && a[x].b <= b[qb].b)
	{
		ufs.merge(a[x].u, a[x].v, a[x].a, a[x].b);
	}
}

void addb(int x)
{
	if (~qa && b[x].a <= a[qa].a)
	{
		ufs.merge(b[x].u, b[x].v, b[x].a, b[x].b);
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	
	a.resize(m);
	
	for (int i = 0; i < m; ++i) scanf("%d%d%d%d", &a[i].u, &a[i].v, &a[i].a, &a[i].b);
	b = a;
	
	sort(a.begin(), a.end(), cmpa);
	sort(b.begin(), b.end(), cmpb);
	
	scanf("%d", &k);
	
	B = m / sqrt(k) + 1;
	
	q.resize(m / B + 1);
	
	ans.resize(k);
	
	for (int i = 0; i < k; ++i)
	{
		int u, v, ra, rb;
		scanf("%d%d%d%d", &u, &v, &ra, &rb);
		int aa = upper_bound(a.begin(), a.end(), Edge(ra, rb), cmpa) - a.begin() - 1;
		int bb = upper_bound(b.begin(), b.end(), Edge(ra, rb), cmpb) - b.begin() - 1;
		if (~aa && ~bb) q[aa / B].emplace_back(u, v, aa, bb, ra, rb, i);
		else ans[i] = false;
	}
	
	for (int i = 0; i < q.size(); ++i)
	{
		sort(q[i].begin(), q[i].end());
		ufs.reset();
		qb = -1;
		qa = i * B;
		
		for (auto t : q[i])
		{
			while (qb < t.b) addb(++qb);
			ufs.record();
			while (qa < t.a) adda(++qa);
			ufs.check(t);
			ufs.rollback();
			qa = i * B;
		}
	}
	
	for (auto x : ans) puts(x ? "Yes" : "No");
	
	return 0;
}