[POI2018]Powódź

题目

Description

在地面上有一个水箱，它的俯视图被划分成了n行m列个方格，相邻两个方格之间有一堵厚度可以忽略不计的墙，水箱与外界之间有一堵高度无穷大的墙，因此水不可能漏到外面。已知水箱内每个格子的高度都是[0,H]之间的整数，请统计有多少可能的水位情况。因为答案可能很大，请对10^9+7取模输出。两个情况不同当且仅当存在至少一个方格的水位在两个情况中不同。

Input

第一行包含三个正整数n,m,H(n*m<=500000,1<=H<=10^9)。接下来n行，每行m-1个整数a[i]j，表示(i,j)和(i,j+1)之间的墙的高度。接下来n-1行，每行m个整数b[i]j，表示(i,j)和(i+1,j)之间的墙的高度。

Output

输出一行一个整数，即方案数模10^9+7的结果。

Sample Input

Sample Output

HINT

要么全部格子水位都是2，要么全部格子水位都在[0,1]之间，共1+2^6=65种情况。

题解

如果水位比格子$x$四周最低的墙高，那么与$x$连通的比$x$低的格子一定都是这个高度

所以把墙从低到高枚举，每次合并墙两边的格子$x,y$，方案数为$(num_x+h(x,y)-h_y)\times (num_y+h(x,y)-h_x)$（两边分水是否全没过）

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define pu(x,y) (x-1)*m+y
# define LL long long
using namespace std;
const int MAX=5e5+5,mod=1e9+7;
struct p{
    int x,y,h;
    bool operator< (const p &a)
    const{
        return h<a.h;
    }
}wall[MAX*2];
int n,m,h,num;
int fa[MAX];
LL qwq[MAX],H[MAX];
int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
int main()
{
    scanf("%d%d%d",&n,&m,&h);
    for(int i=1;i<=n;++i)
      for(int j=1;j<m;++j)
        wall[++num]=(p){pu(i,j),pu(i,j+1)},scanf("%d",&wall[num].h);
    for(int i=1;i<n;++i)
      for(int j=1;j<=m;++j)
        wall[++num]=(p){pu(i,j),pu(i+1,j)},scanf("%d",&wall[num].h);
    for(int i=1;i<=n*m;++i)
      qwq[i]=1,H[i]=0,fa[i]=i;
    sort(wall+1,wall+1+num);
    for(int i=1,r1,r2;i<=num;++i)
      {
        r1=find(wall[i].x),r2=find(wall[i].y);
        if(r1==r2) continue;
        qwq[r1]=(qwq[r1]+wall[i].h-H[r1])*(qwq[r2]+wall[i].h-H[r2])%mod,H[r1]=wall[i].h,fa[r2]=r1;
      }
    int qaq=find(1);
    return printf("%lld",(qwq[qaq]+h-H[qaq]+mod)%mod);
}

题目