【SDOI2019】世界地图

发表于
https://loj.ac/problem/3112

题目链接

【SDOI2019】世界地图

做法

因为 $ n $ 很小，所以问题可以从 $ n $ 入手。
发现询问不会删除第一列和最后一列，那么最后的结果为合并地图 $ [1, l_i - 1] $ 和 $ [r_i + 1, m] $ 的 $ MST $ 得到的 $ MST $ 大小。所以预处理只要求地图前缀/后缀 $ MST $ 即可。
考虑如何合并两个相邻的 $ MST $ 。发现合并这两个 $ MST $ 只有最前和最后两列的点会产生连接的关系，所以每个 $ MST $ 只要记录两端的点构成的虚树（虚树边权为两点之间路径的最大值），然后再用 $ Kruskal $ 建最小生成树即可。
时间复杂度 $ O(n(m + q) \log n) $ 。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 20010, M = 510;
int n, m, lim, q;
unsigned int SA, SB, SC;
int rht[N][M], dwn[N][M];

struct Edge {
	int x, y, w;
	Edge(int X, int Y, int W) : x(X), y(Y), w(W) {}
	inline bool operator<(const Edge &yy)const { return w < yy.w; }
};

int tot, fa[N], flag[N]; vector<Edge> e; ll ad;
int cnt = 0, hed[N], to[N], nxt[N], val[N];

struct MST {
	int tot; ll sum; vector<Edge> e; MST() {}
	MST(int *ar) {
		tot = n, sum = 0;
		for(int i = 1; i < n; i++) e.pb(Edge(i, i + 1, ar[i]));
	}
	ll qry() { ll ss = sum; for(auto v : e) ss += v.w; return ss; }
}; MST pre[N], suf[N];

inline int Max(const int &x, const int &y) { return x > y ? x : y; }
int gi() {
	SA ^= SA << 16, SA ^= SA >> 5, SA ^= SA << 1; unsigned int t = SA;
	SA = SB, SB = SC, SC ^= t ^ SA; return SC % lim + 1;
}
void gen() {
	scanf("%d%d%u%u%u%d", &n, &m, &SA, &SB, &SC, &lim);
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) rht[j][i] = gi();
	for(int i = 1; i < n; i++) for(int j = 1; j <= m; j++) dwn[j][i] = gi();
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void lnk(const Edge &x) {
	to[++cnt] = x.y, val[cnt] = x.w, nxt[cnt] = hed[x.x], hed[x.x] = cnt;
	to[++cnt] = x.x, val[cnt] = x.w, nxt[cnt] = hed[x.y], hed[x.y] = cnt;
	ad += x.w, fa[find(x.x)] = find(x.y);
}
int dfs1(int u, int ff) {
	int ss = 0;
	for(int i = hed[u]; i; i = nxt[i]) if(to[i] != ff) ss += dfs1(to[i], u);
	if(ss >= 2) flag[u] = 1; ss += flag[u]; return ss > 0;
}
void dfs2(int u, int ff, int lst, int ww) {
	if(flag[u]) {
		if(lst) e.pb(Edge(flag[u], lst, ww));
		lst = flag[u], ad -= ww, ww = 0;
	}
	for(int i = hed[u]; i; i = nxt[i])
		if(to[i] != ff) dfs2(to[i], u, lst, Max(ww, val[i]));
}
MST merge(const MST &x, const MST &y, int *ar) {
	tot = x.tot + y.tot, e.clear();
	for(auto v : x.e) e.pb(v);
	for(auto v : y.e) e.pb(Edge(v.x + x.tot, v.y + x.tot, v.w));
	for(int i = 1; i <= n; i++)
		e.pb(Edge(x.tot - n + i, x.tot + i, ar[i]));
	sort(e.begin(), e.end()), cnt = 0, ad = 0;
	for(int i = 1; i <= tot; i++)
		fa[i] = i, flag[i] = (i <= n || i > tot - n), hed[i] = 0;
	for(auto v : e) if(find(v.x) != find(v.y)) lnk(v);
	dfs1(1, 0), cnt = 0;
	for(int i = 1; i <= tot; i++) if(flag[i]) flag[i] = ++cnt;
	e.clear(), dfs2(1, 0, 0, 0);
	MST res; res.tot = cnt, res.e = e, res.sum = x.sum + y.sum + ad;
	return res;
}
int main() {
	gen();
	pre[1] = MST(dwn[1]);
	for(int i = 2; i < m; i++)
		pre[i] = merge(pre[i - 1], MST(dwn[i]), rht[i - 1]);
	suf[m] = MST(dwn[m]);
	for(int i = m - 1; i > 1; i--)
		suf[i] = merge(MST(dwn[i]), suf[i + 1], rht[i]);
	scanf("%d", &q);
	for(int l, r; q; --q) {
		scanf("%d%d", &l, &r);
		printf("%lld\n", merge(suf[r + 1], pre[l - 1], rht[m]).qry());
	}
	return 0;
}