奇度边集 / Pastoral Oddities

题目链接：YBT2022寒假Day8 B / luogu CF603E

题目大意

给你一个 n 个点的图，然后一开始没有边，依次加边，然后每次问你当前是否存在一个边集，使得所有点度数都是奇数。
如果存在输出选的边权的最大边权的最小值，如果不存在输出 -1。

思路

首先我们要考虑存在点集所有点度数都是奇数的边需要怎样。
先说结论：需要不存在奇数个点的连通块。

首先证明奇数的肯定不行，不难看到那奇数个点，每个都是奇数个度数，那总度数就是奇数，但是一条边提供两个度数，总度数肯定是偶数，所以肯定不行。
然后证明偶数的行，我们可以对它做树形 DP，从根往上，连接没有连接的，已经连接的就不选它跟父亲的边，不难看出一定可以匹配完。

然后接着考虑怎么最小化边集的边权，不难想到一个类似最小生成树的算法。

然后这时候其实是可以用 LCT 来搞，就每次加边不断尝试删最小生成树中边权最大的边（用堆维护这些边），如果删到不合法了，那最后的边就是答案（也不能删了）。

但是这里我们也可以用 cdq 分治来做。
我们考虑把边按权值排序，然后我们设当前询问的区间（这里按插入时间排）为 $[l,r]$，答案区间为 $[L,R]$（这里是按权值排序的顺序）。

然后就是对于一个位置 $mid$ 求它的答案。
我们考虑用并查集维护，那首先我们要把 $[l,mid]$ 中在 $[1,L-1]$ 的边给放进去。

然后我们看看在 $[L,R]$ 中的边，如果它的位置在 $[1\sim mid]$ 就放进去，如果发现没有没有奇数连通块了，那就是当时的位置对于边的权值。
然后我们假设求出来的答案是 $ans$。

那显然我们要处理一些东西：
在处理 $[mid+1,r]$ 之前，我们要处理 $[l,mid]$ 中在 $[1,L-1]$ 的部分。
在处理 $[l,mid-1]$ 之前，我们要处理 $[L,ans]$ 权值之间的 $[1\sim l-1]$ 时间出现的给加入。

然后两边是分开的，所以我们要用的是可撤回并查集。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;struct node {int x, y, w, pl;
}a[300001], b[300001];
int n, m, pl[300001];
int ans[300001];bool cmp(node x, node y) {return x.w < y.w;
}struct Heap {int fa[300001], sz[300001], tot, sta[300001];void Init() {tot = n; for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;}int find(int now) {if (fa[now] == now) return now;return find(fa[now]);}void connect(int x, int y) {int X = find(x), Y = find(y);if (X == Y) return ;if (sz[X] > sz[Y]) swap(X, Y), swap(x, y);fa[X] = Y; tot -= (sz[X] & 1) + (sz[Y] & 1);sz[Y] += sz[X]; tot += (sz[Y] & 1);sta[++sta[0]] = X;}void back() {int X = sta[sta[0]], Y = fa[X];tot -= (sz[Y] & 1); sz[Y] -= sz[X];tot += (sz[X] & 1) + (sz[Y] & 1); fa[X] = X;sta[0]--;}
}H;void clac(int mid, int l, int r, int L, int R) {int lst = H.sta[0];for (int i = l; i <= mid; i++)if (pl[i] < L) H.connect(b[i].x, b[i].y);for (int i = L; i <= R; i++) {if (a[i].pl <= mid) {H.connect(a[i].x, a[i].y);if (!H.tot) {ans[mid] = i; break;}}}while (H.sta[0] > lst) H.back();
}void cdq(int l, int r, int L, int R) {if (l > r) return ;int mid = (l + r) >> 1;clac(mid, l, r, L, R);if (!ans[mid]) {for (int i = l; i <= mid; i++)if (pl[i] < L) H.connect(b[i].x, b[i].y);cdq(mid + 1, r, L, R);return ;}int lst = H.sta[0];for (int i = L; i <= ans[mid]; i++)if (a[i].pl < l) H.connect(a[i].x, a[i].y);cdq(l, mid - 1, ans[mid], R);while (H.sta[0] > lst) H.back();lst = H.sta[0];for (int i = l; i <= mid; i++)if (pl[i] < L) H.connect(b[i].x, b[i].y);cdq(mid + 1, r, L, ans[mid]);while (H.sta[0] > lst) H.back();
}int main() {scanf("%d %d", &n, &m);for (int i = 1; i <= m; i++) {scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].w); a[i].pl = i;}memcpy(b, a, sizeof(b)); H.Init();sort(a + 1, a + m + 1, cmp);for (int i = 1; i <= m; i++)pl[a[i].pl] = i;cdq(1, m, 1, m);for (int i = 1; i <= m; i++)printf("%d\n", ans[i] ? a[ans[i]].w : -1);return 0;
}