[SDOI2019] 世界地圖

其實這題在 2024 年就應該寫了，一直拖到現在，要不是因為模擬賽因為沒做過這個題導致 T1 墜機了我可能都忘記補了。

題解

每次詢問就是讓你求一個點集的最小生成樹。
相當于求把一個前綴 \([1,l-1]\) 的最小生成樹和后綴 \([r+1,m]\) 的最小生成樹，通過 \((i,m)-(i,1)\) 的邊連接起來合并之后的新的最小生成樹。
而一個前綴（后綴同理）\([1,j]\) 的最小生成樹也可以認為是前綴 \([1,j-1]\) 的最小生成樹和第 \(j\) 列的最小生成樹用 \((i,j-1)-(i,j)\) 的邊合并之后的最小生成樹。
所以我們只需要知道怎么合并兩棵最小生成樹就可以了。

首先你得知道最小生成樹有一個用 LCT 維護的求法，就是每次加進來一條邊 \((u,v,w)\) 時如果 \(u,v\) 不連通直接選，否則看一下目前 \(u,v\) 路徑上的邊權最大的邊 \(l\) 和 \(w\) 哪個大，保留更小的那個。（知道思想即可，畢竟最后還是用 Kruskal 求的）。
以求前綴的最小生成樹為例，因為合并前綴 \([1,j-1]\) 和第 \(j\) 列時，新加的那 \(n\) 條邊只會影響第 \(j-1\) 和 \(j\) 列的點，我們稱這兩列的點為關鍵點。那么有且僅有兩個關鍵點之間的路徑上的最大邊可能會被替換，其他最小生成樹上的邊在之后都不會變化了，所以我們可以對最小生成樹上的那些關鍵點建立虛樹，邊權就設為最小生成樹上兩點之間的路徑上的最大邊權。那么原圖的最小生成樹的邊權和就可以看成是虛樹上的邊權和 \(+\) 不在虛樹上的邊權和。這里主要講前者怎么維護，后者比較簡單直接根據代碼理解即可。
合并時把兩棵最小生成樹對應的兩棵虛樹上的點和邊拿出來，加上新加的那 \(n\) 條邊一起跑一個 Kruskal，得到一個新的最小生成樹 \(T\)。然后我們找出新圖的那些關鍵點，并在 \(T\) 上對他們建立虛樹就得到了新圖的虛樹，邊權仍然是路徑上的最大邊。
Tip：因為 \(T\) 的點數很少，和關鍵點是同一個數量級的，所以直接跑兩遍 dfs 建虛樹即可，沒有必要二次排序，后者常數反而更大。

需要注意的是關鍵點既可能是最左側一列的點，也可能是最右側一列的點，但是我們沒有必要對最左側和最右側的點分別維護虛樹，因為眾所周知不管往虛樹里多加多少點都不影響正確性，所以直接把最左側和最右側的點全設為關鍵點然后一起維護虛樹即可。

容易發現任何時刻虛樹的規模都是 \(O(n)\) 級別的（最大差不多是 \(8n\)），所以暴力跑 Kruskal 求最小生成樹的復雜度是 \(O(n\log n)\)，總復雜度是 \(O(n(m+q)\log n)\)。

code

#include<bits/stdc++.h>
#define LL long long  
using namespace std;
const int N=1e2+5,M=1e4+5,N2=N*8;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,T,a[M][N],b[M][N]; 
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;
}
struct Edge{ int u,v,w; };
struct MST{
	int num;  //點數，維護的時候需要保證編號最小的 n 個點是最左側一列的點，編號最大的 n 個點是最右側一列的點 
	LL sum;  //存儲之后不可能再被修改的邊的邊權和 
	vector<Edge> E;
	void Init(int w[]){
		num=n,sum=0;
		for(int i=1;i<n;i++) E.push_back({i,i+1,w[i]});
	} 
	LL ask(){
		LL ans=sum;
		for(Edge e:E) ans+=e.w;
		return ans;
	}
}pre[M],suf[M];
int fa[N2],id[N2];
LL ans;
int get(int x){return (x==fa[x])?x:(fa[x]=get(fa[x]));}
int tot,head[N2],to[N2<<1],Next[N2<<1],val[N2<<1];
void add(int u,int v,int w){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot,val[tot]=w;
}
bool dfs1(int u,int fa){  //dfs 建虛樹 
	int c=0;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa) continue;
		c+=dfs1(v,u);
	}
	if(c>=2) id[u]=1;   
	return id[u]||c;
}
vector<Edge> newE;
void dfs2(int u,int fa,int lst,int maxn){
	if(id[u]){
		if(lst){
			newE.push_back({lst,id[u],maxn});
			ans-=maxn;  
			/*
				只有一條鏈上的最大邊之后才有可能被刪掉，剩余的最小生成樹上的邊之后都不會被刪，
				ans 維護的就是那些最小生成樹上不會被刪的邊 
			*/ 
		}
		lst=id[u],maxn=0;
	}
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa) continue;
		dfs2(v,u,lst,max(maxn,val[i]));
	}
}
MST Merge(MST T1,MST T2,int w[]){
	int num=T1.num+T2.num;
	vector<Edge> E=T1.E;
	for(Edge e:T2.E) E.push_back({e.u+T1.num,e.v+T1.num,e.w});
	for(int i=1;i<=n;i++) E.push_back({T1.num-n+i,T1.num+i,w[i]});
	sort(E.begin(),E.end(),[&](Edge e1,Edge e2){return e1.w<e2.w;});
	
	ans=0,tot=0;
	for(int i=1;i<=num;i++) fa[i]=i,head[i]=0,id[i]=((i<=n)||(i>=num-n+1)); //前 n 個和后 n 個點是關鍵點 
	for(Edge e:E){
		int u=e.u,v=e.v,w=e.w;
		if(get(u)==get(v)) continue;
		ans+=w,fa[get(u)]=get(v);
		add(u,v,w),add(v,u,w);
	}
	
	dfs1(1,0); 
	int cnt=0;
	for(int i=1;i<=num;i++) if(id[i]) id[i]=++cnt;  //給所有虛樹上的點重標號
	newE.clear();
	dfs2(1,0,0,0);
	MST T3;
	T3.num=cnt,T3.sum=T1.sum+T2.sum+ans,T3.E=newE;
	return T3;
} 
void Init(){
	for(int i=1;i<=m;i++) pre[i].Init(b[i]),suf[i].Init(b[i]);
	for(int i=2;i<=m;i++) pre[i]=Merge(pre[i-1],pre[i],a[i-1]);
	for(int i=m-1;i>=1;i--) suf[i]=Merge(suf[i],suf[i+1],a[i]);
}
signed main(){
    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++){
			a[j][i]=getweight();
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			b[j][i]=getweight();
		}
	}
	
	Init();
	
	scanf("%d",&T);
	while(T--){
		int l,r; scanf("%d%d",&l,&r);
		printf("%lld\n",Merge(suf[r+1],pre[l-1],a[m]).ask());
	}
	return 0;
}