题面

\(\text{Solution:}\)

显然在线算法根本不可做，先将询问离线，按 \(b\) 排序。

注意到不一定是简单路径，所以一个询问回答为 \(Yes\) 当且仅当 \(u，v\) 在同一个连通块中且该连通块中边最大值 \(a\) 与最大值 \(b\) 与询问的 \(a，b\) 相等。

所以我们考虑用带权并查集维护联通块。

所以我们将询问也按 \(b\) 排序，对于一个询问 \(q[i]\) , 将 \(b<q[i].b\) 的边塞入并查集中，再将 \(a<q[i].a\) 的边也塞入并查集中，这样并查集中的边就是所有 \(a<q[i].a,b<q[i].b\) ，然后记录答案，记录完后将刚刚插入的 \(a<q[i].a\) 的边再撤销，继续处理下一个询问。

由于要支持撤销操作，用按秩合并，不能路径压缩。

由于b有序且单调，所以插入 \(b\) 是 \(O(n)\) ，插入 \(a\) 与撤销 \(a\) 也 \(O(nlogn)\) 的，总复杂度 \(O(n^2logn)\)。

然后我们发现复杂度过高的瓶颈在于 \(a\) 的插入是 \(O(nlogn)\) 的而且插入了许多没有必要插入的信息(那些远小于 \(q[i].a\) 的边), 考虑对 \(a\) 分块，将复杂度均摊。

将 \(a\) 排序，分块，对于一个块 \(x\) ，它所对应的并查集包含了 \(a\le a[size * x]\) 的所有边。

当我们插入一条 \(b\le q[i].b\) 的边时，需要二分查找到这条边 \(a\) 所在的块，然后将该块一直到最后一个块的并查集中都插入这一条边，对于 \(\le q[i].a\) 的边，我们就可以找到最大的开头 \(\le q[i].a\) 的块，然后将这块开头到 \(q[i].a\) 都塞进这一块所对应的并查集(因为在这块之前的块里的边显然都小于 $q[i].a $)，查询也在这一块中进行(显然 \(b<q[i].b\) 的边都在这块的并查集里).

总复杂度 \(O(nlogn\sqrt{n})​\).

#include <set> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <assert.h> #include <algorithm>using namespace std;#define LL long long #define debug(...) fprintf(stderr, __VA_ARGS__) #define GO debug("GO\n")inline int rint() {register int x = 0, f = 1; register char c;while (!isdigit(c = getchar())) if (c == '-') f = -1;while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));return x * f; }template<typename T> inline void chkmin(T &a, T b) { a > b ? a = b : 0; } template<typename T> inline void chkmax(T &a, T b) { a < b ? a = b : 0; }const int N = 1e5 + 100;struct Edge {int u, v, a, b, id;bool operator< (const Edge &B) const {return a < B.a;}} fir[N<<1], sec[N<<1], q[N<<1];bool cmp_a(const Edge &a, const Edge &b) {return a.a < b.a; }bool cmp_b(const Edge &a, const Edge &b) {return a.b < b.b; }int top;struct Ifm {int type, x, y, z;} stk[N<<1];struct Union_Set {int fa[N], size[N], max_a[N], max_b[N];int Find(int x) {while (fa[x]) x = fa[x];return x;}void Merge(int x, int y, int a, int b, int op) {int Fx = Find(x), Fy = Find(y);if (size[Fx] > size[Fy]) swap(Fx, Fy), swap(x, y);if (op == 1)stk[++top] = (Ifm) { 1, Fy, max_a[Fy], max_b[Fy] };chkmax(max_a[Fy], max(max_a[Fx], a));chkmax(max_b[Fy], max(max_b[Fx], b));if (Fx == Fy) return;fa[Fx] = Fy;size[Fy] += size[Fx];if (op == 1)stk[++top] = (Ifm) { 0, Fx, Fy, size[Fx] };}void Backdate() {while (top) {if (stk[top].type == 0) {fa[stk[top].x] = 0;size[stk[top].y] -= stk[top].z;} else {max_a[stk[top].x] = stk[top].y;max_b[stk[top].x] = stk[top].z;}--top;}}int Query(int x, int y, int a, int b) {int anc = Find(x);if (x == y and a == 0 and b == 0)return size[anc] != 1;if (anc != Find(y)) return 0;if (max_a[anc] != a or max_b[anc] != b) return 0;return 1;} } U[1005];int n, m, K; int ans[N], front[N];int main() { #ifndef ONLINE_JUDGEfreopen("xhc.in", "r", stdin);freopen("xhc.out", "w", stdout); #endifn = rint(), m = rint();for (int i = 1; i <= m; ++ i) {fir[i].u = rint();fir[i].v = rint();fir[i].a = rint();fir[i].b = rint();sec[i] = fir[i];}K = rint();for (int i = 1; i <= K; ++ i) {q[i].u = rint();q[i].v = rint();q[i].a = rint();q[i].b = rint();q[i].id = i;}int SIZE = sqrt(m * 20), Block_Cnt = m / SIZE;for (int i = 0; i <= Block_Cnt; ++ i) for (int j = 1; j <= n; ++ j)U[i].size[j] = 1;sort(fir + 1, fir + 1 + m, cmp_a);sort(sec + 1, sec + 1 + m, cmp_a);for (int i = 0; i <= Block_Cnt; ++ i)front[i] = sec[i * SIZE].a;sort(q + 1, q + 1 + K, cmp_b);sort(sec + 1, sec + 1 + m, cmp_b);int pos = 1;for (int i = 1; i <= K; ++ i) {while (sec[pos].b <= q[i].b and pos <= m) {int block = lower_bound(front, front + 1 + Block_Cnt, sec[pos].a) - front;for (int j = block; j <= Block_Cnt; ++ j) {U[j].Merge(sec[pos].u, sec[pos].v, sec[pos].a, sec[pos].b, 0);}pos++;}int P = upper_bound(front, front + Block_Cnt + 1, q[i].a) - front - 1;Edge tp; tp.a = front[P];int tpos = upper_bound(fir + 1, fir + 1 + m, tp) - fir;while (fir[tpos].a <= q[i].a and tpos <= m) {if (fir[tpos].b <= q[i].b) {U[P].Merge(fir[tpos].u, fir[tpos].v, fir[tpos].a, fir[tpos].b, 1);}++tpos;}ans[q[i].id] = U[P].Query(q[i].u, q[i].v, q[i].a, q[i].b);U[P].Backdate();}for (int i = 1; i <= K; ++ i)ans[i] == 1 ? puts("Yes") : puts("No");return 0; }

转载于:https://www.cnblogs.com/cnyali-Tea/p/10614100.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的[HNOI2016]最小公倍数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。