SDOI2019 世界地图

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

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

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

复杂度 O(nmlogn)O(nm\log n)log\logkruskal 中的排序。

#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();
}
\