Pastoral Oddities

题面

给定一张 $n$ 个点的无向图，初始没有边。

依次加入 $m$ 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。

若存在，则还需要最小化边集中的最大边权。

$n \le 10^5$ ， $m \le 3 \times 10^5$ 。

题解

线段树分治好题。

每条边要么选不了，要么选完后被取代再也回不来。这就是在时间的一个区间了。值得注意的是，这题在分治过程中覆盖，还是很有意思的。

代码

const int N = 3e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int odd, pos;
	int ans[N];
	int fa[N], siz[N];
	int find(int k) { return k == fa[k]? k: find(fa[k]); }
	struct stack_node {
		int u, v, val;
	} st[N]; 
	int top;
	void Merge (int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return;
		if (siz[u] < siz[v]) swap(u, v);
		st[++top] = (stack_node) { u, v, 0 };
		if ((siz[u] & 1) && (siz[v] & 1)) odd -= 2, st[top].val += 2;
		siz[u] += siz[v]; fa[v] = u;
	}
	struct edge {
		int u, v, val, id;
		bool operator < (const edge &a) const { return val < a.val; }
	} ed[N];
	vector <edge> v[N << 2];
	void Modify (int p, int l, int r, int L, int R, edge val) {
		if (L <= l && r <= R) { v[p].push_back(val); return; }
		int mid = (l + r) >> 1;
		if (L <= mid) Modify (p << 1, l, mid, L, R, val);
		if (R > mid) Modify (p << 1 | 1, mid + 1, r, L, R, val);
	}
	void Solve (int p, int l, int r) {
		int ltop = top;
		for (auto e: v[p]) Merge(e.u, e.v);
		int mid = (l + r) >> 1;
		if (l == r) {
			for (; odd && pos < m; pos++) {
				if (ed[pos + 1].id <= l) {
					Merge (ed[pos + 1].u, ed[pos + 1].v);
					if (ed[pos + 1].id < l) Modify (1, 1, m, ed[pos + 1].id, l - 1, ed[pos + 1]);
				}
			}
			if (odd) ans[l] = -1;
			else ans[l] = ed[pos].val;
		} else Solve (p << 1 | 1, mid + 1, r), Solve(p << 1, l, mid);
		for (; top != ltop; top--) {
			siz[st[top].u] -= siz[st[top].v]; fa[st[top].v] = st[top].v;
			odd += st[top].val;
		}
	}
	int main () {
		odd = n = Read(), m = Read();
		for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
		for (int i = 1; i <= m; i++) ed[i].u = Read(), ed[i].v = Read(), ed[i].val = Read(), ed[i].id = i;
		sort (ed + 1, ed + 1 + m);
		Solve (1, 1, m);
		for (int i = 1; i <= m; i++) printf ("%d\n", ans[i]);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}