[DS记录]P5360 [SDOI2019]世界地图
command_block
·
·
个人记录
题意 ： 一个左右相接的 n\times m 网格图，边有边权。
每次挖掉一个区间的列之后，求剩余部分的 \rm MST 边权和。
------------
先预处理前缀生成树和后缀生成树，然后想办法合并。合并时会加入连接列 $1,n$ 的一列边。
对第一列和最后一列的点在生成树上建立虚树，每条虚树边中只会有一条最大的边可能被断开。
我们只需要维护端点虚树的最大边集合。
类似地，每加入一列边时，也只有最大边集合中的边可能被断开。
我们将图简化成只有虚树，和新加入的边一起跑 $\rm Kruskal$ 。将剩余的边形成的结构化简为虚树（缩二度点）。
当询问时，也只需要合并两组虚树的边。
一次合并的复杂度为 $O(n\log n)$ ，总复杂度为 $O((m+q)n\log n)$。
若使用归并排序，可以做到 $O(n\alpha(n))$ 合并。
大常数代码 ：
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define uint unsigned int
#define MaxN 10050
#define MaxM 105
#define ll long long
using namespace std;
vector<int> g[MaxN*MaxM],l[MaxN*MaxM];
int st[MaxN<<4],tn;
void adl(int u,int v,int w){
g[u].pb(v);l[u].pb(w);
g[v].pb(u);l[v].pb(w);
}
void clrg()
{
for (int i=1;i<=tn;i++){
g[st[i]].clear();
l[st[i]].clear();
}tn=0;
}
ll tsum;
struct Line{int u,v,w;};
vector<Line> sl2;
bool side[MaxN*MaxM],siz[MaxN*MaxM];
int down[MaxN*MaxM],len[MaxN*MaxM];
void dfs(int u,int fa)
{
st[++tn]=u;
int cnt=2*(siz[u]=side[u]);
down[u]=u;len[u]=0;
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=fa){
dfs(v,u);
cnt+=siz[v];
siz[u]|=siz[v];
}
bool fl=(cnt>1||!fa);
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=fa){
if (siz[v]){
if (fl){
if (len[v]>l[u][i])
{sl2.pb((Line){u,down[v],len[v]});tsum+=l[u][i];}
else {sl2.pb((Line){u,down[v],l[u][i]});tsum+=len[v];}
}else {
down[u]=down[v];
len[u]=max(len[v],l[u][i]);
tsum+=min(len[v],l[u][i]);
}
}else tsum+=len[v]+l[u][i];
}
}
bool cmpL(const Line &A,const Line &B)
{return A.w<B.w;}
struct VMST
{
vector<Line> s;
ll sum;
void smpfy()
{
for (int i=0;i<s.size();i++)
adl(s[i].u,s[i].v,s[i].w);
tsum=0;sl2.clear();
dfs(s[0].u,0);
sum+=tsum;s=sl2;
clrg();
}
ll calc(){
ll ret=0;
for (int i=0;i<s.size();i++)
ret+=s[i].w;
return ret;
}
}tl[MaxN],tr[MaxN];
uint SA,SB,SC;int lim;
int getweight() {
SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;
uint t=SA;
SA=SB;SB=SC;SC^=t^SA;
return SC%lim+1;
}
int n,m,l0[MaxN][MaxM],l1[MaxN][MaxM];
void gen(){
scanf("%d%d%u%u%u%d",&m,&n,&SA,&SB,&SC,&lim);
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)
l0[i][j]=getweight();
for(int j=1;j<m;j++)
for(int i=1;i<=n;i++)
l1[i][j]=getweight();
}
int f[MaxN*MaxM];
void clrf(){
for (int i=1;i<=tn;i++)
f[st[i]]=st[i];
tn=0;
}
int find(int u)
{return f[u]==u ? u : f[u]=find(f[u]);}
bool merge(int u,int v){
u=find(u);v=find(v);
if (u==v)return 0;
f[u]=v;return 1;
}
void merge(VMST &T,vector<Line> &s)
{
for (int i=0;i<T.s.size();i++)s.pb(T.s[i]);
sort(s.begin(),s.end(),cmpL);
T.s.clear();
for (int i=0;i<s.size();i++)
if (merge(s[i].u,s[i].v)){
T.s.pb(s[i]);
st[++tn]=s[i].u;
st[++tn]=s[i].v;
}
clrf();
}
vector<Line> sl;
#define tp(i,j) ((i-1)*m+j)
int main()
{
gen();
for (int i=1;i<=n*m;i++)f[i]=i;
for (int j=1;j<=m;j++)side[tp(1,j)]=side[tp(n,j)]=1;
for (int j=1;j<m;j++)
tl[1].s.pb((Line){tp(1,j),tp(1,j+1),l1[1][j]});
for (int i=2;i<n;i++){
sl.clear();
for (int j=1;j<m;j++)sl.pb((Line){tp(i,j),tp(i,j+1),l1[i][j]});
for (int j=1;j<=m;j++)sl.pb((Line){tp(i-1,j),tp(i,j),l0[i-1][j]});
for (int j=1;j<=m;j++)side[tp(i,j)]=1;
tl[i]=tl[i-1];merge(tl[i],sl);tl[i].smpfy();
for (int j=1;j<=m;j++)side[tp(i,j)]=0;
}
for (int j=1;j<m;j++)
tr[n].s.pb((Line){tp(n,j),tp(n,j+1),l1[n][j]});
for (int i=n-1;i>1;i--){
sl.clear();
for (int j=1;j<m;j++)sl.pb((Line){tp(i,j),tp(i,j+1),l1[i][j]});
for (int j=1;j<=m;j++)sl.pb((Line){tp(i,j),tp(i+1,j),l0[i][j]});
for (int j=1;j<=m;j++)side[tp(i,j)]=1;
tr[i]=tr[i+1];merge(tr[i],sl);tr[i].smpfy();
for (int j=1;j<=m;j++)side[tp(i,j)]=0;
}
int q;scanf("%d",&q);
while(q--){
int l,r;scanf("%d%d",&l,&r);l--;r++;
VMST T=tl[l];sl=tr[r].s;
for (int j=1;j<=m;j++)sl.pb((Line){tp(n,j),tp(1,j),l0[n][j]});
merge(T,sl);
printf("%lld\n",tl[l].sum+tr[r].sum+T.calc());
}
}
```