专栏文章

题解：P13342 [EGOI 2025] Wind Turbines / 风力涡轮机

lliangjindong0504
P13342题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio7xi2b
此快照首次捕获于
2025/12/02 14:50
3 个月前
此快照最后确认于
2025/12/02 14:50
3 个月前
查看原文

前言

使用回滚莫队通过了这一道题，感谢 yingkeqian9217 的点拨。同时以较大的优势抢下最劣解。
疯狂的提交记录
警告
本人实现比较抽象，代码又臭又长，请谨慎阅读。

Part 1

首先，这个题面好抽象啊，考虑把它转化一下。
不难发现，答案其实就是原图中将 l∼rl \sim r 这一段的点缩成一个点，然后求整张图的 MST（最小生成树）中边的权值和。于是我们考虑先将整个图的 MST 求出来。

Part 2

考虑每次询问中 ri=li+1r_i = l_i + 1，即 Subtask 3。将两个点缩成一个点之后，显然相当于在两点之间加一条权值为 0 的边，然后继续求 MST。于是显然，这部分的答案就是 s−wmaxs - w_{max}，ss 是原图 MST 的权值，wmaxw_{max} 是 ll 到 rr 最小生成树的路径上权值最大值。
然后你可以获得 13 分。注意到我的代码中把点的编号都加了 1，个人习惯。

Part 3

接下来我们引入 kruskal 重构树。
所谓 kruskal 重构树，就是先按建 MST 的过程，按照边权从小到大排序。然后，当两点在并查集中祖先不是相同的，就考虑将它们合并，同时新开一个点，这两点的祖先为该点的儿子。
同时，我们将这个新开的点的点权设为这条边的权值。
接着，我们会发现一些有趣的事情。
在草稿纸上画出样例的 kruskal 重构树，然后在询问中可以发现，其实用一个 flag 数组，每次询问的时候给两两之间在 kruskal 重构树上的 LCA 打上 tag，最后用 MST 的权值减去这些被标记的点的权值即可。
对于这一点我也是感性理解的，个人的感觉是考虑 kruskal 过程，两个点只能在合并处节约。也就是一开始先是两点之间被连了一条权值为 0 的边，那么原先 合并的地方就不用合并了。只有 11 分。
两份代码合并起来就以后 24pts 了！！！
实际上用莫队乱搞一下也可以获得 24 分。提交记录。

Part 4

接下来的这个做法可以获得 54 分。
我们还是考虑莫队。之前的莫队之所以慢，显然是因为每次插入或者删除的时候都要把其他的都扫一遍。这显然是很慢的。那么我们考虑，能不能对于添加、删除做到更优的复杂度？
首先我们需要做到 O(1)O(1) 求 LCA 。预处理 O(nlog⁡n)O(n\log n)。
发现，两个点之间的 LCA 只跟它们的 dfs 序（dfn）有关。为何？我们发现，设两个点为 u,vu,v 且 dfnu<dfnvdfn_u < dfn_v，它们的 LCA 为 tt，那么显然，tt 到 vv 的这段路径（除去 tt）上的所有点的 dfs 序都在 dfnudfn_u 到 dfnvdfn_v 之间。
那么显然，两点的 LCA 就是所有 xx，满足 dfnu≤dfnx≤dfnvdfn_u \le dfn_x \le dfn_v 中 depdep 最小的节点的父亲。depxdep_x 表示 xx 的深度。
接下来我们说明，扩展或者删除的时候，被标记的点的数量只会变化 11。这点可以从 Part 1 中得到。因为扩展的时候，相当于边权为 00 的边又多了一条，可以少打一个 tag。删除同理，即多打一个 tag。
不难发现，加入一个点的时候，我们寻找的是它和其他已经处理过的点中所有 LCA 深度最大的点。原因很简单，因为如果不是深度最大的点，那么一定是这个点的祖先，并且一定之前已经打过 tag 了。
换一种角度理解，也就是说，对于找到的那个点的祖先，与被加入点同侧的一定有另一个叶子，于是这个点要么不是新加点与原有点的 LCA，要么已经被打过 tag 了。
随后，我们考虑使用 set 维护 dfn 序，每次插入删除可以 O(log⁡n)O(\log n) 完成。于是，我们可以 O(nnlog⁡n)O(n \sqrt n \log n) 解决。期望得分 54 分，下面是代码。卡卡就过了。
54 分代码CPP
#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

const int MAXN = 2e5 + 10;
const int INF  = 1e9;

struct node {
	int x;
	i64 val;

	bool operator < (const node &tmp) const {
		return x < tmp.x;
	}
};

struct DSU {
	int n;
	std::vector <int> fa;
	DSU (int n_) : n(n_), fa(n + 10) {};

	void init() {
		for (int i = 1; i <= n; ++i) {
			fa[i] = i;
		}
	}

	int find (int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
};

struct EDGE {
	int u, v;
	i64 w;

	bool operator < (const EDGE &tmp) const {
		return w < tmp.w;
	}
};

struct EDGE2 {
	int to, w;
};

int B;

struct QUESTION {
	int l, r, id;
	i64 ans;

	bool operator < (const QUESTION &tmp) const {
		int nl = (l + B - 1) / B;
		int pl = (tmp.l + B - 1) / B;
		if (nl == pl) {
			if (nl % 2) {
				return r < tmp.r;
			} else {
				return tmp.r < r;
			}
		}
		return nl < pl;
	}
};

bool cmp (QUESTION x, QUESTION y) {
	return x.id < y.id;
}

int n, m, q;
int dep[MAXN];
int dfn[MAXN];
int st[MAXN][20];
int stid[MAXN][20];

int tot;
int tot1;

int fa[MAXN];

i64 val[MAXN];
i64 tag[MAXN];

i64 s, ans;

EDGE e[MAXN];
QUESTION ask[MAXN];

std::vector <int> edge;
std::vector <int> mst[MAXN];
std::vector <node> pos[MAXN];

void dfs (int x, int lst) {
	dfn[x] = ++tot1;
	fa[dfn[x]] = lst;
	dep[x] = dep[lst] + 1;
	st[dfn[x]][0] = st[dfn[lst]][0] + 1;
	stid[dfn[x]][0] = dfn[x];

	for (auto to : mst[x]) {
		if (to == lst) {
			continue;
		}

		dfs(to, x);
	}
}

int lg[MAXN];
int o[MAXN];

std::set <int> f;

node rmq (int l, int r) {
	if (l > r) std::swap(l, r);
	int k = lg[r - l + 1];
	int k1 = st[l][k], k2 = st[r - (1 << k) + 1][k];
	if (k1 < k2) {
		return (node){stid[l][k], k1};
	} else {
		return (node){stid[r - (1 << k) + 1][k], k2};
	}
}

void add (int x) {
	if (!f.size()) {
		f.insert(dfn[x]);
		return;
	}

	int maxn = 0;
	int p;

	auto cur = f.insert(dfn[x]).first;
	auto suf = cur;
	auto pre = suf;
	++suf;
	if (pre != f.begin()) {
		--pre;
		int s = *pre + 1;
		int t = dfn[x];

		node u = rmq(s, t);
		if (u.val > maxn) {
			maxn = u.val;
			p = u.x;
		}
	}

	if (suf != f.end()) {
		int t = *suf;
		int s = dfn[x] + 1;

		node u = rmq(s, t);
		if (u.val > maxn) {
			maxn = u.val;
			p = u.x;
		}
	}
	ans -= val[fa[p]];
}

void del (int x) {
	int maxn = -1;
	int p;

	auto cur = f.find(dfn[x]);
	auto suf = cur;
	++suf;
	f.erase(cur);
	auto pre = suf;
	if (pre != f.begin()) {
		--pre;
		int s = *pre + 1;
		int t = dfn[x];

		node u = rmq(s, t);
		if (u.val > maxn) {
			maxn = u.val;
			p = u.x;
		}
	}
	if (suf != f.end()) {
		int t = *suf;
		int s = dfn[x] + 1;

		node u = rmq(s, t);
		if (u.val > maxn) {
			maxn = u.val;
			p = u.x;
		}
	}
	ans += val[fa[p]];
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	lg[0] = -1;
	for (int i = 1; i <= 2e5; ++i) {
		lg[i] = lg[i / 2] + 1;
	}
	
	std::cin >> n >> m >> q;
	B = sqrt(n / 2);
	for (int i = 1; i <= m; ++i) {
		std::cin >> e[i].u >> e[i].v >> e[i].w;
		++e[i].u, ++e[i].v;
	}
	std::sort(e + 1, e + m + 1);

	DSU dsu(n * 2 - 1);
	dsu.init(); 
	tot = n;
	for (int i = 1; i <= m; ++i) {
		int fu = dsu.find(e[i].u);
		int fv = dsu.find(e[i].v);
		if (fu != fv) {
			s += e[i].w;
			dsu.fa[fu] = dsu.fa[fv] = ++tot;

			val[tot] = e[i].w;
			mst[tot].push_back(fu);
			mst[tot].push_back(fv);
		}
	}

	dfs(n * 2 - 1, 0);
	for (int j = 1; j <= 19; ++j) {
		for (int i = 1; i <= n * 2 - 1 - (1 << j) + 1; ++i) {
			st[i][j] = std::min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
			if (st[i][j] == st[i][j - 1]) {
				stid[i][j] = stid[i][j - 1];
			} else {
				stid[i][j] = stid[i + (1 << j - 1)][j - 1];
			}
		}
	}

	for (int i = 1; i <= q; ++i) {
		std::cin >> ask[i].l >> ask[i].r;
		++ask[i].l, ++ask[i].r;
		ask[i].id = i;
	}
	std::sort(ask + 1, ask + q + 1);

	ans = s;
	int nl = 1, nr = 0;
	for (int i = 1; i <= q; ++i) {
		while (nl > ask[i].l) {
			add(--nl);
		}
		while (nr < ask[i].r) {
			add(++nr);
		}
		while (nl < ask[i].l) {
			del(nl++);
		}
		while (nr > ask[i].r) {
			del(nr--);
		}
		ask[i].ans = ans;
	}

	std::sort(ask + 1, ask + q + 1, cmp);
	for (int i = 1; i <= q; ++i) {
		std::cout << ask[i].ans << std::endl;
	}

	return 0;
}
提交记录

Part 5

我们发现添加和删除复杂度还是太劣了。
发现，我们可以记录前驱和后继。每次删除的时候直接把前驱和后继处理一下就能够 O(1)O(1) 实现。但是这个时候添加操作的复杂度仍然是 O(log⁡n)O(\log n)。但是！看到只允许删除，不允许添加，你想到了什么？回滚莫队！
没学过回滚莫队的建议先去看板子，里面题解应该是讲得比较详细的。这里简单提一下。
考虑把询问的 ll 逐块处理，到新的块的时候全部推翻重来，将前驱后继全部重新处理。这里可以先记录另一个前驱后继，右端点为 nn，左端点不断增加。显然只有删除操作。
对于同一个块中的，我们考虑先记录这个块的左端点，然后右端点原来先从大到小排好序，一开始从 n 开始，不断删除。对于左边的，从这个块的左端点往右删除，用一个栈记录变化。当这一次询问处理结束之后，根据栈内记录的信息，往回推。
最后时间复杂度是 O(nn)O(n \sqrt n)，稍微卡一卡常就过了。
100 分代码CPP
#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

const int MAXN = 2e5 + 10;
const int INF  = 1e9;

struct node {
	int x;
	i64 val;

	bool operator < (const node &tmp) const {
		return x < tmp.x;
	}
};

struct DSU {
	int n;
	std::vector <int> fa;
	DSU (int n_) : n(n_), fa(n + 10) {};

	void init() {
		for (int i = 1; i <= n; ++i) {
			fa[i] = i;
		}
	}

	int find (int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
};

struct OPERATE {
	int pre, x, suf;
};

struct EDGE {
	int u, v;
	i64 w;

	bool operator < (const EDGE &tmp) const {
		return w < tmp.w;
	}
};

struct EDGE2 {
	int to, w;
};

int B;
int block[MAXN];

struct QUESTION {
	int l, r, id;
	i64 ans;

	bool operator < (const QUESTION &tmp) const {
		int nl = block[l];
		int pl = block[tmp.l];
		if (nl == pl) {
			return tmp.r < r;
		}
		return nl < pl;
	}
};

bool cmp (QUESTION x, QUESTION y) {
	return x.id < y.id;
}

int n, m, q;
int dep[MAXN];
int dfn[MAXN];
int st[MAXN][20];
int stid[MAXN][20];

int tot;
int tot1;

int fa[MAXN];

i64 val[MAXN];
i64 tag[MAXN];

i64 s, ans;

EDGE e[MAXN];
QUESTION ask[MAXN];

std::vector <int> edge;
std::vector <int> mst[MAXN];
std::vector <node> pos[MAXN];

void dfs (int x, int lst) {
	dfn[x] = ++tot1;
	fa[dfn[x]] = lst;
	dep[x] = dep[lst] + 1;
	st[dfn[x]][0] = st[dfn[lst]][0] + 1;
	stid[dfn[x]][0] = dfn[x];

	for (auto to : mst[x]) {
		if (to == lst) {
			continue;
		}

		dfs(to, x);
	}
}

int lg[MAXN];
int o[MAXN];

int now_block;
int gpre[MAXN];
int gsuf[MAXN];
int tpre[MAXN];
int tsuf[MAXN];

i64 tval, res;

std::set <int> f;

inline node rmq (int l, int r) {
	if (l > r) std::swap(l, r);
	int k = lg[r - l + 1];
	int k1 = st[l][k], k2 = st[r - (1 << k) + 1][k];
	if (k1 < k2) {
		return (node){stid[l][k], k1};
	} else {
		return (node){stid[r - (1 << k) + 1][k], k2};
	}
}

int tp;
OPERATE stk[MAXN];

inline void add (int pre, int x, int suf, i64 &tval) {
	int maxn = -1;
	int p;

	if (!pre && !suf) {
		return;
	}
	if (pre) {
		int s = pre + 1;
		int t = x;

		node u = rmq(s, t);
		if (u.val > maxn) {
			maxn = u.val;
			p = u.x;
		}
	}
	if (suf) {
		int t = suf;
		int s = x + 1;

		node u = rmq(s, t);
		if (u.val > maxn) {
			maxn = u.val;
			p = u.x;
		}
	}
	tval -= val[fa[p]];
}

inline void del (int x, bool opt, i64 &tval) {
	int maxn = -1;
	int p;

	int pre = tpre[x];
	int suf = tsuf[x];
    
	if (!pre && !suf) {
		return;
	}
	if (pre) {
		int s = pre + 1;
		int t = x;

		node u = rmq(s, t);
		if (u.val > maxn) {
			maxn = u.val;
			p = u.x;
		}
	}
	if (suf) {
		int t = suf;
		int s = x + 1;

		node u = rmq(s, t);
		if (u.val > maxn) {
			maxn = u.val;
			p = u.x;
		}
	}
	tval += val[fa[p]];
	
	if (opt) {
		stk[++tp]=(OPERATE){pre, x, suf};
	}
	tsuf[pre] = suf;
	tpre[suf] = pre;
}
inline void del2 (int x, bool opt, i64 &tval) {
	int maxn = -1;
	int p;

	int pre = gpre[x];
	int suf = gsuf[x];
    
	if (!pre && !suf) {
		return;
	}
	if (pre) {
		int s = pre + 1;
		int t = x;

		node u = rmq(s, t);
		if (u.val > maxn) {
			maxn = u.val;
			p = u.x;
		}
	}
	if (suf) {
		int t = suf;
		int s = x + 1;

		node u = rmq(s, t);
		if (u.val > maxn) {
			maxn = u.val;
			p = u.x;
		}
	}
	tval += val[fa[p]];
	
	if (opt) {
		stk[++tp]=(OPERATE){pre, x, suf};
	}
	gsuf[pre] = suf;
	gpre[suf] = pre;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	std::cin >> n >> m >> q;
	B = 380;
	lg[0] = -1;
	for (int i = 1; i <= 2e5; ++i) {
		lg[i] = lg[i / 2] + 1;
		block[i] = (i + B - 1) / B;
	}
	for (int i = 1; i <= m; ++i) {
		std::cin >> e[i].u >> e[i].v >> e[i].w;
		++e[i].u, ++e[i].v;
	}
	std::sort(e + 1, e + m + 1);

	DSU dsu(n * 2 - 1);
	dsu.init(); 
	tot = n;
	for (int i = 1; i <= m; ++i) {
		int fu = dsu.find(e[i].u);
		int fv = dsu.find(e[i].v);
		if (fu != fv) {
			s += e[i].w;
			dsu.fa[fu] = dsu.fa[fv] = ++tot;

			val[tot] = e[i].w;
			mst[tot].push_back(fu);
			mst[tot].push_back(fv);
		}
	}

	dfs(n * 2 - 1, 0);
	for (int j = 1; j <= 17; ++j) {
		for (int i = 1; i <= n * 2 - 1 - (1 << j) + 1; ++i) {
			st[i][j] = std::min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
			if (st[i][j] == st[i][j - 1]) {
				stid[i][j] = stid[i][j - 1];
			} else {
				stid[i][j] = stid[i + (1 << j - 1)][j - 1];
			}
		}
	}

	for (int i = 1; i <= q; ++i) {
		std::cin >> ask[i].l >> ask[i].r;
		++ask[i].l, ++ask[i].r;
		ask[i].id = i;
	}
	std::sort(ask + 1, ask + q + 1);

	std::vector <int> e;
	for (int i = 1; i <= n; ++i) {
		e.push_back(dfn[i]);
	}
	std::sort(e.begin(), e.end());
	for (int i = 0; i < e.size(); ++i) {
		if (i) {
			gpre[e[i]] = e[i - 1];
		}
		if (i < e.size() - 1) {
			gsuf[e[i]] = e[i + 1];
		}
	}

	ans = s;
	int nl = 1, nr = 0;

	now_block = 0;
	for (int i = 1; i <= q; ++i) {
		if (block[ask[i].l] != now_block) {
			while (now_block != block[ask[i].l]) {
				if (now_block >= 1) {
					int tl = (now_block - 1) * B + 1;
					int tr = now_block * B;
					for (int j = tl; j <= tr; ++j) {
						del2(dfn[j], 0, tval);
					}
				}

				++now_block;
			}
			for (int j = std::max(1, (now_block - 1) * B + 1); j <= n; ++j) {
				tpre[dfn[j]] = gpre[dfn[j]], tsuf[dfn[j]] = gsuf[dfn[j]];
			}
			res = tval;

			nl = (now_block - 1) * B + 1;
			nr = n;
        }

		while (nr > ask[i].r) {
			del(dfn[nr], 0, res);
			--nr;
		}

		int el = nl;
		while (el < ask[i].l) {
			del(dfn[el], 1, res);
			++el;
		}

		//std::cout << "O:" << ask[i].l << ' ' << ask[i].r << ' ' << res << std::endl;
		ask[i].ans = res;
		while (tp) {
			OPERATE tmp = stk[tp--];

			tsuf[tmp.pre] = tmp.x;
			tpre[tmp.suf] = tmp.x;

			tpre[tmp.x] = tmp.pre;
			tsuf[tmp.x] = tmp.suf;
			add(tmp.pre, tmp.x, tmp.suf, res);
		}
	}

	std::sort(ask + 1, ask + q + 1, cmp);
	for (int i = 1; i <= q; ++i) {
		std::cout << ask[i].ans << "\n";
	}

	return 0;
}
提交记录

后记

本人的实现方式真的是太离谱了（（（
如果有错误请指出。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...