首页 > 代码库 > Codeforces 603E Pastoral Oddities
Codeforces 603E Pastoral Oddities
传送门：http://codeforces.com/problemset/problem/603/E
【题目大意】
给出$n$个点，$m$个操作，每个操作加入一条$(u, v)$长度为$l$的边。
对于每次操作后，求出一个边集，使得每个点度数均为奇数，且边集的最大边最小。
$n \leq 10^5, m \leq 3 * 10^5$
【题解】
有结论：满足条件（每个点度数均为奇数），当且仅当每个连通块大小都是偶数（容易证明，从下往上，调整法）。
那么显然可以LCT维护连通性，连通块大小以及最大边位置，每次拉出最大边，加入即可。做法有点像水管局长那题。
复杂度$O((n+m)log(n+m))$，常数大……LCT太不优美了！！！
考虑一种优美的做法：
这个类似于动态维护生成树（生成森林），那么是否可以分治？
答案是可以的。一开始我们往整体二分的方向想，发现没有办法支持并查集的撤销，然后就gg了。实际上这道题有一个非常优美的分治做法！
【手动分割】
容易发现把-1看成inf，那么答案是不增的。
定义$solve(l, r, lo, hi)$表示目前处理的操作区间为$[l, r]$，答案区间为$[lo, hi]$。
那么考虑求出$mid = (l+r)/2$的时候的答案$ans[mid]$。
那么我们是不是可以根据$mid$和$ans[mid]$，划分成$solve(l, mid-1, ans[mid], hi)$和$solve(mid+1, r, lo, ans[mid])$来分治！！！
想到这里了，问题在于怎样求出$ans[mid]$以及划分区间需要进行的并查集操作。
这里的并查集容易发现，要使用按秩合并，不能路径压缩，因为要支持撤销。（支持撤销的并查集套路有很多，比如bzoj连通图、二分图那几题）
考虑求$ans[mid]$，我们画一张图，横坐标代表询问id，纵坐标代表length。
（字母要用光了QAQ）
我们目标是求出ans[mid]的这条线从而划分成BFQG和DEQH来分治，目前的区域为ABCD。
因为我们要求mid的答案，相当于求Q点的坐标。所以$[l,mid-1]$的边相当于已经加了。
考虑矩形DHYX，表示$[l, mid-1]$的边，权值范围小于$lo$，容易发现这个对于我们统计$mid$的答案是必须加入的，加入即可。
接下来按从小到大的顺序依次加入每一条权值在$[lo, hi]$的边，然后实时记录是否满足条件了，如果满足，那么我们就能求出$ans[mid]$。
求完$ans[mid]$要撤销并查集操作哦~
那么这步就做完了，下面就有两个问题了。
1. 找不到$ans[mid]$，那么说明$[l, mid]$都没有解，就能把DHYX的所有边加入并查集中了，然后递归寻找$solve(mid+1, r, lo, hi)$即可，记得撤销操作。
2. 找到了$ans[mid]$：
这个就非常兹磁了对吧，我们就可以分成两块做了。
考虑如果递归到$solve(mid+1, r, lo, ans[mid])$，那么同样的，DHYX的所有边也可以被加入并查集中了。
考虑如果递归到$solve(l, mid-1, ans[mid], hi)$，那么，STDE中的所有边也可以被加入并查集中了。
那么维护这个东西就行了。
容易发现，每条边最多被加入$O(logm)$次，每次复杂度为$O(logn)$，所以复杂度为$O(mlogmlogn)$，由于常数小，实测跑的飞快。
【手动分割-2】
真的跑的飞快吗？
第一次测：TLE on test 83（代码见下）
# include <vector> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 3e5 + 10, N = 1e5 + 10; const int mod = 1e9+7; int n, m, mx; struct op { int a, b, l, sl; }q[M]; vector<int> v[M], ps; struct us { struct backup { int x, y, del; } st[N]; int stn; int fa[N], sz[N], cnt_odd; inline void set(int n) { cnt_odd = n; stn = 0; for (int i=1; i<=n; ++i) fa[i] = i, sz[i] = 1; } inline int getf(int x) { return fa[x] == x ? x : getf(fa[x]); } inline void un(int x, int y) { x = getf(x), y = getf(y); if(x == y) return ; if(sz[x] < sz[y]) swap(x, y); ++stn; if((sz[x] & 1) && (sz[y] & 1)) cnt_odd -= 2, st[stn].del = 2; else st[stn].del = 0; st[stn].x = x, st[stn].y = y; sz[x] += sz[y]; fa[y] = x; } inline void re() { backup s = st[stn--]; cnt_odd += s.del; sz[s.x] -= sz[s.y]; fa[s.y] = s.y; } inline bool check() { return cnt_odd == 0; } }S; int ans[M]; inline void solve(int l, int r, int lo, int hi) { if(l > r) return ; // now doing intervals [l, r], the answer is in [lo, hi] // find the answer of mid = (l+r)/2 int mid = l+r>>1, ans_mid = -1, lst = S.stn; // add in edges that in interval [l, mid], and satisfy length < lo for (int i=l; i<=mid; ++i) if(q[i].sl < lo) S.un(q[i].a, q[i].b); // add in edges from [lo] to [hi], and find the answer of mid for (int i=lo; i<=hi; ++i) { for (int j=0; j<v[i].size(); ++j) if(v[i][j] <= mid) S.un(q[v[i][j]].a, q[v[i][j]].b); // if satisfy the condition if(S.check()) { ans_mid = i; break; } } while(S.stn > lst) S.re(); if(ans_mid == -1) { // cannot find the answer of mid for (int i=l; i<=mid; ++i) ans[i] = -1; // add in edges that in interval [l, mid], and satisfy length < lo for (int i=l; i<=mid; ++i) if(q[i].sl < lo) S.un(q[i].a, q[i].b); solve(mid+1, r, lo, hi); while(S.stn > lst) S.re(); return ; } // set the answer of mid to ans_mid // so to interval [l, mid], the answer is [ans_mid, hi]; // to interval [mid+1, r], the answer is [lo, ans_mid]. ans[mid] = ans_mid; // for the right side [mid+1, r], we can add in edges that in [l, mid], and satisfy length < lo. for (int i=l; i<=mid; ++i) if(q[i].sl < lo) S.un(q[i].a, q[i].b); solve(mid+1, r, lo, ans_mid); while(S.stn > lst) S.re(); // for the left side [l, mid], we can add in edges that satisfy length < ans_mid, and in [1, l) for (int i=lo; i<ans_mid; ++i) for (int j=0; j<v[i].size(); ++j) if(v[i][j] < l) S.un(q[v[i][j]].a, q[v[i][j]].b); solve(l, mid-1, ans_mid, hi); while(S.stn > lst) S.re(); } int main() { cin >> n >> m; S.set(n); if(n & 1) { while(m --) puts("-1"); return 0; } for (int i=1; i<=m; ++i) { scanf("%d%d%d", &q[i].a, &q[i].b, &q[i].l); ps.push_back(q[i].l); } sort(ps.begin(), ps.end()); ps.erase(unique(ps.begin(), ps.end()), ps.end()); for (int i=1; i<=m; ++i) { q[i].sl = lower_bound(ps.begin(), ps.end(), q[i].l) - ps.begin() + 1; v[q[i].sl].push_back(i); } solve(1, m, 1, ps.size()); for (int i=1; i<=m; ++i) { if(ans[i] == -1) puts("-1"); else printf("%d\n", ps[ans[i]-1]); } return 0; }
感受了下原因，这是一个$n = 8, m = 2.6 * 10^5$的非常稠密图。我之前的写法是离散，用vector维护每种值有多少，然后会出现的问题是$ans[mid]$可能很长时间不动，那么访问$ans[mid]$里所有的值是近似$O(m)$复杂度，所以肯定爆炸了啊！
有两种解决方法，一种加入id，表示是$ans[mid]$中的第$id$个节点达到答案；一种是用排序后的边的下标来替代值，那么$lo$和$hi$就变成了边的下标。
我设排序前数组为q，排序后为p。
然后我还傻逼WA了一次，因为我直接把q[i].l和p[lo].l比大小，小于就加入，如果有q[i].l=p[lo].l，就很难分清楚要不要加入了，这个的解决办法是对于q加入一个id表示在p中的位置，那么就兹磁比大小了。
现在跑的飞快了！
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 3e5 + 10, N = 1e5 + 10; const int mod = 1e9+7; int n, m; struct op { int a, b, l, id; friend bool operator < (op a, op b) { return a.l < b.l; } }q[M], p[M]; struct us { struct backup { int x, y, del; } st[N]; int stn; int fa[N], sz[N], cnt_odd; inline void set(int n) { cnt_odd = n; stn = 0; for (int i=1; i<=n; ++i) fa[i] = i, sz[i] = 1; } inline int getf(int x) { return fa[x] == x ? x : getf(fa[x]); } inline void un(int x, int y) { x = getf(x), y = getf(y); if(x == y) return ; if(sz[x] < sz[y]) swap(x, y); ++stn; if((sz[x] & 1) && (sz[y] & 1)) cnt_odd -= 2, st[stn].del = 2; else st[stn].del = 0; st[stn].x = x, st[stn].y = y; sz[x] += sz[y]; fa[y] = x; } inline void re() { backup s = st[stn--]; cnt_odd += s.del; sz[s.x] -= sz[s.y]; fa[s.y] = s.y; } inline bool check() { return cnt_odd == 0; } }S; int ans[M]; inline void solve(int l, int r, int lo, int hi) { if(l > r) return ; // CAUTION!!! [lo, hi] cannot be real number, it must be the index of the array!!! // now doing intervals [l, r], the answer is in [lo, hi] // find the answer of mid = (l+r)/2 int mid = l+r>>1, ans_mid = -1, lst = S.stn; // add in edges that in interval [l, mid], and satisfy length < lo (that is, number < lo for (int i=l; i<=mid; ++i) if(q[i].id < lo) S.un(q[i].a, q[i].b); // add in edges from [lo] to [hi], and find the answer of mid for (int i=lo; i<=hi; ++i) { if(p[i].id <= mid) S.un(p[i].a, p[i].b); // if satisfy the condition if(S.check()) { ans_mid = i; break; } } while(S.stn > lst) S.re(); if(ans_mid == -1) { // cannot find the answer of mid for (int i=l; i<=mid; ++i) ans[i] = -1; // add in edges that in interval [l, mid], and satisfy length < lo for (int i=l; i<=mid; ++i) if(q[i].id < lo) S.un(q[i].a, q[i].b); solve(mid+1, r, lo, hi); while(S.stn > lst) S.re(); return ; } // set the answer of mid to ans_mid // so to interval [l, mid], the answer is [ans_mid, hi]; // to interval [mid+1, r], the answer is [lo, ans_mid]. ans[mid] = p[ans_mid].l; // for the right side [mid+1, r], we can add in edges that in [l, mid], and satisfy length < lo. for (int i=l; i<=mid; ++i) if(q[i].id < lo) S.un(q[i].a, q[i].b); solve(mid+1, r, lo, ans_mid); while(S.stn > lst) S.re(); // for the left side [l, mid], we can add in edges that satisfy length < ans_mid, and in [1, l) for (int i=lo; i<ans_mid; ++i) if(p[i].id < l) S.un(p[i].a, p[i].b); solve(l, mid-1, ans_mid, hi); while(S.stn > lst) S.re(); } int main() { cin >> n >> m; S.set(n); if(n & 1) { while(m --) puts("-1"); return 0; } for (int i=1; i<=m; ++i) { scanf("%d%d%d", &q[i].a, &q[i].b, &q[i].l); p[i] = q[i]; p[i].id = i; } sort(p+1, p+m+1); for (int i=1; i<=m; ++i) q[p[i].id].id = i; solve(1, m, 1, m); for (int i=1; i<=m; ++i) printf("%d\n", ans[i]); return 0; }
Codeforces 603E Pastoral Oddities