洛谷P3247 [HNOI2016]最小公倍数(分块 带撤销加权并查集)

时间：2023-03-10 03:12:40
洛谷P3247 [HNOI2016]最小公倍数(分块 带撤销加权并查集)

题意

题目链接

给出一张带权无向图，每次询问\((u, v)\)之间是否存在一条路径满足\(max(a) = A, max(b) = B\)

Sol

这题居然是分块。。想不到想不到。。做这题的心路历程大概可以写个800字的作文。

\(warning:\)下面的做法复杂度是错的。但是可以过

以下是attack的心路历程

考场上不会做，然后看了一眼题解发现可以对\(a\)分块。

怎么分呢？我们可以对边按\(a\)分块，然后把每个询问先按\(b\)排序后扔到对应的\(a\)所在的块内

这个时候\(b\)的限制就好搞了，每个块都是递增的，之前的块可以预处理之后排序，复杂度\(m\sqrt{m}\log m\)是可以接受的。

块内的呢？好像暴力就可以了，直接拿个启发式合并的可撤销带权并查集搞，维护一下路径最大值。复杂度也是\(m \sqrt{m} log m\)，但是枚举的上界必须是\(M\)不然会wa(\(a\)相同\(b\)不相同)，算了先交一发。。

然后交上去->80..

把T掉的数据下载下来发现居然有\(a\)全都相同的点。。。

emmmmmm，开始面向数据编程，每次询问的时候可以把每个块内询问\(a\)的最小值拿出来，按\(b\)排序之后双指针搞。

然后就过了，复杂度显然是不对的。只要来个\(a\)很小的数据就G了。

以下代码充满了attack对人生的思考，，，请谨慎观看

#include<bits/stdc++.h>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

//#define int long long

#define LL long long

#define Fin(x) {freopen(#x".in","r",stdin);}

#define Fout(x) {freopen(#x".out","w",stdout);}

using namespace std;

const int MAXN = 1e6 + 10, mod = 998244353, INF = 2e9 + 10;

const double eps = 1e-9;

template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}

template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}

template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}

template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}

template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}

template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}

template <typename A> inline void debug(A a){cout << a << '\n';}

template <typename A> inline LL sqr(A x){return 1ll * x * x;}

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, M, Q, block, belong[MAXN], ll[MAXN], rr[MAXN], mx, ans[MAXN];

struct Edge {

	int u, v, a, b, id;

	bool operator < (const Edge &rhs) const {

		return a == rhs.a ? b < rhs.b : a < rhs.a;

	}

}E[MAXN], q[MAXN], st[MAXN], fuck1[MAXN];

vector<Edge> fuck2;

int comp(const Edge &x, const Edge &y) {

	return x.b == y.b ? x.a < y.a : x.b < y.b;

}

vector<Edge> v[MAXN];

int vis[MAXN], num, fa[MAXN], mxa[MAXN], mxb[MAXN], siz[MAXN];

struct Sta {

	int x, ta, tb, si;

};

Sta inst[MAXN];

int find(int x) {

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

}

void Add(Edge &e) {

	int x = e.u, y = e.v, a = e.a, b = e.b;

	int fx = find(x), fy = find(y);

	if(fx == fy) {

		inst[++num] = {fx, mxa[fx], mxb[fx], siz[fx]};

		inst[++num] = {fy, mxa[fy], mxb[fy], siz[fy]};

		chmax(mxa[fx], a); chmax(mxb[fx], b);

		return ;

	}

	if(siz[fx] > siz[fy]) swap(fx, fy), swap(x, y);

	inst[++num] = {fx, mxa[fx], mxb[fx], siz[fx]};

	inst[++num] = {fy, mxa[fy], mxb[fy], siz[fy]};

	siz[fy] += siz[fx];

	chmax(mxa[fy], a); chmax(mxb[fy], b);

	chmax(mxa[fy], mxa[fx]); chmax(mxb[fy], mxb[fx]);

	fa[fx] = fy;

}

void Erase(int tim) {

	while(num > tim) {

		Sta pre = inst[num--];

		fa[pre.x] = pre.x; mxa[pre.x] = pre.ta; mxb[pre.x] = pre.tb; siz[pre.x] = pre.si;

	}

}

void solve() {

	int top = 0;

	for(int i = 1; i <= N; i++) fa[i] = i, siz[i] = 1, mxa[i] = mxb[i] = -1;

	for(int i = 1; i <= mx; i++) {

		int now = 1;  int gg = num, fucknum = 0, mn = INF; fuck2.clear();

		for(auto &x : v[i]) chmin(mn, x.a);

		for(int j = ll[i]; j <= M; j++)

			if(E[j].a <= mn) fuck1[++fucknum] = E[j];

			else fuck2.push_back(E[j]);

		sort(fuck1 + 1, fuck1 + fucknum + 1, comp);

		int cur = 0;

		for(auto &x : v[i]) {

			while(now <= top && st[now].b <= x.b) Add(st[now++]);

			while(cur <= fucknum && fuck1[cur].b <= x.b) Add(fuck1[cur++]);

			int tmp = num;

			for(auto & j : fuck2) {

				if(j.a <= x.a ) {

					if(j.b <= x.b) {

						Add(j);

					}

				} else break;

			}

			int fx = find(x.u), fy = find(x.v);

			if(fx != fy || mxa[fx] != x.a || mxb[fx] != x.b) ans[x.id] = 2;

			else ans[x.id] = 1;

			Erase(tmp);

		}

		Erase(gg);

		for(int j = ll[i]; j <= rr[i]; j++) st[++top] = E[j];

		sort(st + 1, st + top + 1, comp);//�Ѿ�����İ�b�ź���ı�

	}

}

signed main() {

//	Fin(a); Fout(b);

	N = read(); M = read(); block = sqrt(M * log(M));

	for(int i = 1; i <= M; i++) E[i].u = read(), E[i].v = read(), E[i].a = read(), E[i].b = read();

	E[++M] = {-1, -1, INF, INF};

	sort(E + 1, E + M + 1);

	for(int i = 1; i <= M; i++) belong[i] = (i - 1) / block + 1, chmax(mx, belong[i]);

	for(int i = 1; i <= mx; i++) ll[i] = (i - 1) * block + 1, rr[i] = min(M, ll[i] + block - 1);//tag

	Q = read();

	for(int i = 1; i <= Q; i++) q[i].u = read(), q[i].v = read(), q[i].a = read(), q[i].b = read(), q[i].id = i;

	sort(q + 1, q + Q + 1, comp);

	for(int i = 1; i <= Q; i++) {

		int pos = lower_bound(E + 1, E + M + 1, q[i]) - E;

		v[belong[pos]].push_back(q[i]);

	}

	solve();

	for(int i = 1; i <= Q; i++) puts(ans[i] == 1 ? "Yes" : "No");

	return 0;

}

相关文章