Yijan's Blog HomeArchives
SDOI2019 世界地图

考虑如果能建立出前后缀的最小生成树，然后就只需要往里面添加开头向结尾的边的问题。

然后会发现，实际上这些边只会连接开头、结尾这 $2n$ 个点，由于断边也只会断这 $2n$ 个点中两两路径上的一些最大边，于是我们考虑维护出每个前缀和后缀的生成树上这 $n$ 个点的虚树，虚树上边权就是路径上边权的最大值。由于这样虚数点数是 $O(n)$ 的，所以甚至可以对每个前缀和后缀的虚树都存下来！

但是怎么维护这样的虚树呢？比如我们维护了 $[1,i]$ 的虚树，考虑加入 $i+1$ 这一列的点求虚树。不难发现只有第 $i$ 列点和后面加入的这一列的点有边相连，所以只需要考虑第 $i$ 列的点两两路径，于是可以干脆把这些点也给作为关键点丢进虚树里，解决这一列后再重新求一边虚树，把上一列丢掉，于是总是可以保证里面点数 $O(n)$ 。然后合并的过程或者加边的过程就是把虚树和新边拿出来做一次 kruskal 即可。

复杂度 $O(nm\log n)$ ，$\log$ 是 kruskal 中的排序。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m , q;
int A[MAXN];

int gid( int x , int y ) {
	return ( x - 1 ) * m + y;
}

int R[106][10006] , D[106][10006] ;
int cnt;

unsigned int SA, SB, SC;int lim;
int getweight() {
    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);
    int i, j, w;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++) {
            w = getweight();
        	R[i][j] = w;
        }
    for(i = 1; i < n; i++)
        for(j = 1; j <= m; j++) {
            w = getweight();
            D[i][j] = w;
        }
}

struct ed {
	int u , v , w;
	ed() : u(0) , v(0) , w(0) {}
	ed( int u , int v , int w ) : u(u) , v(v) , w(w) { }
};
vector<ed> pr[10006] , su[10006];
ll pw[MAXN] , sw[MAXN];

void ot( vector<ed>& x ) {
	for( auto t : x ) printf("%d %d %d\n",t.u,t.v,t.w);
}

vector<pii> G[MAXN];
int fa[MAXN];
int find( int x ) {
	return x == fa[x] ? x : fa[x] = find( fa[x] );
}
ll kru( vector<ed>& E ) { // sum of weight not in MST
	sort( all( E ) , []( ed& a , ed& b ) { return a.w < b.w; } );
	ll as = 0;
	for( auto& t : E ) G[t.u].clear() , G[t.v].clear() , fa[t.u] = t.u , fa[t.v] = t.v;
	for( auto& t : E ) {
		int u = find( t.u ) , v = find( t.v );
		if( u != v ) {
			G[t.u].eb( t.v , t.w ) , G[t.v].eb( t.u , t.w );
			fa[v] = u;
		} else as += t.w;
	}
	return as;
}

int fk[MAXN] , sz[MAXN];
int ff[MAXN] , wf[MAXN];
vi nd;
void dfs( int u , int f ) {
	ff[u] = f;
	sz[u] = fk[u];
	int so = 0;
	for( auto t : G[u] ) if( t.fi != f ) {
		int v = t.fi;
		wf[v] = t.se;
		dfs( v , u );
		sz[u] |= sz[v];
		if( sz[v] ) ++ so;
	}
	if( so > 1 ) fk[u] = 1;
	if( fk[u] ) nd.pb( u );
}

vector<ed> doit( int s ) {
	vector<ed> re;
	nd.clear();
	dfs( s , s );
	for( int x : nd ) if( x != s ) {
		int w = wf[x] , t = ff[x];
		while( !fk[t] ) w = max( w , wf[t] ) , t = ff[t];
		re.eb( t , x , w );
	}
	return re;
}

vector<ed> ht;
ll wt;

ll merge( int l , int r ) {
	vector<ed> S = pr[l];
	S.insert( S.end() , all( su[r] ) );
	S.insert( S.end() , all( ht ) );
//	ot( S );
	return pw[l] + sw[r] + wt - kru( S );
}

void solve() {
	gen();
	rep( i , 1 , n - 1 ) pr[1].eb( gid( i , 1 ) , gid( i + 1 , 1 ) , D[i][1] ) , pw[1] += D[i][1];
	rep( j , 2 , m ) {
		rep( i , 1 , n ) fk[gid( i , j )] = fk[gid( i , 1 )] = 1;
		pr[j] = pr[j - 1] , pw[j] = pw[j - 1];
		rep( i , 1 , n - 1 ) pr[j].eb( gid( i , j ) , gid( i + 1 , j ) , D[i][j] ) , pw[j] += D[i][j];
		rep( i , 1 , n ) pr[j].eb( gid( i , j ) , gid( i , j - 1 ) , R[i][j - 1] ) , pw[j] += R[i][j - 1];
		pw[j] -= kru( pr[j] );
		pr[j] = doit( gid( 1 , 1 ) );
		for( int x : nd ) fk[x] = 0;
	}
	rep( i , 1 , n ) fk[gid( i , 1 )] = fk[gid( i , m )] = 0;
	rep( i , 1 , n - 1 ) su[m].eb( gid( i , m ) , gid( i + 1 , m ) , D[i][m] ) , sw[m] += D[i][m];
	per( j , m - 1 , 1 ) {
		rep( i , 1 , n ) fk[gid( i , j )] = fk[gid( i , m )] = 1;
		su[j] = su[j + 1] , sw[j] = sw[j + 1];
		rep( i , 1 , n - 1 ) su[j].eb( gid( i , j ) , gid( i + 1 , j ) , D[i][j] ) , sw[j] += D[i][j];
		rep( i , 1 , n ) su[j].eb( gid( i , j ) , gid( i , j + 1 ) , R[i][j] ) , sw[j] += R[i][j];
		sw[j] -= kru( su[j] );
		su[j] = doit( gid( 1 , m ) );
		for( int x : nd ) fk[x] = 0;
	}
//	ot( pr[2] );
	rep( i , 1 , n ) ht.eb( gid( i , m ) , gid( i , 1 ) , R[i][m] ) , wt += R[i][m];
	cin >> q;
	rep( i , 1 , q ) {
		int l , r;
		scanf("%d%d",&l,&r);
		if( l == 1 ) printf("%lld\n",sw[r + 1]);
		else if( r == m ) printf("%lld\n",pw[l - 1]);
		else printf("%lld\n",merge( l - 1 , r + 1 ));
	}
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}
文章作者: yijan
文章链接: https://yijan.co/sdoi2019-shi-jie-di-tu/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！