洛谷P3247 [HNOI2016]最小公倍数(分块 带撤销加权并查集)
程序员文章站
2022-04-28 11:11:00
题意 "题目链接" 给出一张带权无向图,每次询问$(u, v)$之间是否存在一条路径满足$max(a) = A, max(b) = B$ Sol 这题居然是分块。。想不到想不到。。做这题的心路历程大概可以写个800字的作文。 $warning:$下面的做法复杂度是错的。但是可以过 以下是attack ......
题意
给出一张带权无向图,每次询问\((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);//�ѿ�����i�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; }
上一篇: 从前后端项目工程化谈起