題面

\(\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]最小公倍数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。