原题链接\
题目大意
\(有一个高度为H的水箱，里面有n*m个格子，每两个相邻的格子之间有一个隔板，问水位总共有多少中可能的情况，对10^9+7取模\)
数据范围
\(1\le n*m\le 500000,1\le H\le 10^9\)
\(先考虑只有两个格子一个隔板的情况，设此隔板高度为a,则在两边都不溢出时，共(a+1)^2种方案\)
\(溢出之后会变为一个格子，此时两个格子的水位一定相同\)
\(考虑a+1是怎么得来的，显然在没溢出时，每个格子水位可以是0,1,2,.....a-1,a,共a+1种情况\)
\(设f_i表示第i个格子所在的连通块合成前(即没有彻底联通)有多少种水位\)
\(h_i表示第i个格子所在的联通块最终联通时要越过的隔板的高度\)
\(则当i,j之间有高为k的隔板时把i和j合并,f_i=f_j=(f_i+k-h_i)*(f_j+k-h_j)\)
\(考虑合并顺序，可以发现进行了合并操作的隔板一定有n*m-1块，且一定在原图的最小生成树上\)
\(于是可以把原图的隔板看作边，跑最小生成树，并同时更新答案\)
\(代码\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,m,H;
int jntm(int x,int y)
{
return x*m+y;
}
struct bian
{
int l,r,v;
friend bool operator<(bian i,bian j)
{
return i.v<j.v;
}
}b[5000009];
int top,f[5000009],h[5000009],ans[5000009];
int find(int x)
{
if(f[x]==x)
return x;
return f[x]=find(f[x]);
}
signed main()
{
cin>>n>>m>>H;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
f[jntm(i,j)]=jntm(i,j);
ans[jntm(i,j)]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++)
{
int x;
cin>>x;
b[++top]={jntm(i,j),jntm(i,j+1),x};
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
b[++top]={jntm(i,j),jntm(i+1,j),x};
}
sort(b+1,b+top+1);
for(int i=1;i<=top;i++)
{
int l=b[i].l,r=b[i].r;
if(find(l)==find(r))
continue;
l=find(l);
r=find(r);
ans[l]=(ans[l]+b[i].v-h[l])*(ans[r]+b[i].v-h[r])%mod;
h[l]=b[i].v;
f[r]=l;
}
int ngm=(ans[find(jntm(1,1))]+H-h[find(jntm(1,1))])%mod;
cout<<(ngm%mod+mod)%mod;
return 0;
}