「CSA72」MST

「CSA72」MST

题目大意：有一个大小为 \(n\) 的无向完全图，\(x, y\) 之间的边权值为 \(a[\min(x,y)][\max(x,y)]\) ，初始为0，进行 \(m\) 次修改，每次将一个矩形的权值加上 \(w\) ，求出最后这张完全图的最小生成树的边权和。\(n,m \leq 100000\)。

解题思路：用 Borůvka 求最小生成树，每一轮求出每一个点所在联通块向外连的一条边权最小的边，并用线段树+扫描线维护最小值以及最小值所在的联通块编号。为了找到不在同一个联通块内的边权最小的边，所以额外记一个次小值，并时刻保证次小值所在的联通块编号与最小值不是同一个，那么要连出去的最小的边一定在这两者之间，总复杂度 \(O(nlog^2n)\)。

code

/*program by mangoyang*/

#include<bits/stdc++.h>

#define inf ((ll)(1e16))

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T & x){

	int ch = 0, f = 0; x = 0;

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

	for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

	if(f) x = -x;

}

#define par pair<ll, ll>

#define fi first

#define se second

const int N = 100005;

struct chino{ int t, l, r, w; } q[N<<2];

int fa[N], n, m, tot, cnt; ll ans;

par tmp[N];

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

struct Node{

	int id[2]; ll val[2];

	inline Node(){ val[0] = val[1] = inf, id[0] = id[1] = 0; }

	inline Node operator + (const int &w){

		Node res = *this;

		return res.val[0] += w, res.val[1] += w, res;

	}

	inline Node operator + (const Node &A){

		Node res, rhs;

		res = (val[0] < A.val[0] ? *this : A);

		rhs = (val[0] < A.val[0] ? A : *this);

		for(int i = 0; i < 2; i++)

			if(ask(rhs.id[i]) != ask(res.id[0]) && rhs.val[i] < res.val[1])

				res.val[1] = rhs.val[i], res.id[1] = rhs.id[i];

		return res;

	}

};

namespace Seg{

	#define lson (u << 1)

	#define rson (u << 1 | 1)

	#define mid (l + r >> 1)

	Node mn[N<<2]; ll tag[N<<2];

	inline void build(int u, int l, int r){

		tag[u] = 0;

		if(l == r){

			mn[u].val[0] = 0, mn[u].val[1] = inf;

			mn[u].id[0] = l, mn[u].id[1] = 0; return;

		}

		build(lson, l, mid), build(rson, mid + 1, r);

		mn[u] = mn[lson] + mn[rson];

	}

	inline void pushdown(int u){

		if(!tag[u]) return;

		mn[lson] = mn[lson] + tag[u], mn[rson] = mn[rson] + tag[u];

		tag[lson] += tag[u], tag[rson] += tag[u], tag[u] = 0;

	}

	inline void change(int u, int l, int r, int L, int R, ll w){

		if(l >= L && r <= R) return (void) (mn[u] = mn[u] + w, tag[u] += w);

		pushdown(u);

		if(L <= mid) change(lson, l, mid, L, R, w);

		if(mid < R) change(rson, mid + 1, r, L, R, w);

		mn[u] = mn[lson] + mn[rson];

	}

}

inline void Bruasolve(){

	Seg::build(1, 1, n);

	for(register int i = 1; i <= n; i++) tmp[i].fi = inf, tmp[i].se = 0;

	int p = 1;

	for(register int i = 1; i <= n; i++){

		while(p <= cnt && q[p].t == i)

			Seg::change(1, 1, n, q[p].l, q[p].r, q[p].w), p++;

		Node x = Seg::mn[1];

		par now = (ask(x.id[0]) != ask(i)) ? make_pair(x.val[0], x.id[0]) : make_pair(x.val[1], x.id[1]);

		if(now.fi < tmp[ask(i)].fi) tmp[ask(i)] = now;

	}

	for(register int i = 1; i <= n; i++) if(fa[i] == i){

		if(ask(tmp[i].se) != i && tmp[i].se) tot++, ans += tmp[i].fi, fa[ask(tmp[i].se)] = i;

	}

}

inline bool cmp(const chino &A, const chino &B){ return A.t < B.t; }

signed main(){

	read(n), read(m);

	for(int i = 1, X1, X2, Y1, Y2, w; i <= m; i++){

		read(X1), read(X2), read(Y1), read(Y2), read(w);

		q[++cnt] = ((chino){X1, Y1, Y2, w});

		q[++cnt] = ((chino){X2 + 1, Y1, Y2, -w});

		q[++cnt] = ((chino){Y1, X1, X2, w});

		q[++cnt] = ((chino){Y2 + 1, X1, X2, -w});

	}

	sort(q + 1, q + cnt + 1, cmp);

	for(int i = 1; i <= n; i++) fa[i] = i;

	while(tot < n - 1) Bruasolve(); cout << ans << endl;

	return 0;

}