[HNOI2016]最小公倍数
題面
\(\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]最小公倍数的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 课后作业3
- 下一篇: 成龙退出林凤娇全资持股公司 吃瓜群众