[USACO14JAN] Ski Course Rating G

题目大意

滑雪场用一个 $N\ast M$ 的整数矩阵表示海拔高度，每个整数表示一个范围在 $10^9$ 的高度。每个格子都可以滑到相邻的格子，爱好者们将会在雪场种尽情享受。有些格子被指定为起点，每个起点都要进行评级以帮助爱好者选择。

定义起点 $p$ 的难度级别 $d$ 定义为满足以下条件的最小值：

1. 从一个格子能滑到相邻的格子时，这两个格子的海拔差不超过 $d$

2. 至少能够到达 $T$ 个格子（包括起点本身）。

你的任务是计算每个起点的难度级别。

$N,M\le 500$。

题解

读完题的我：这不纯整体二分吗，刚好前段时间刚练了整体二分，看我迅速切掉/dy。（自信开写）

（10分钟后）写完了，非常好！交一发！——TLE20。

咋回事，我卡常！我找死循环！我找不到。我看复杂度，byd复杂度是错的。

一怒之下怒了一下，然后就把这题丢了……

（附一份整体二分代码看乐子）

#include<bits/stdc++.h>
using namespace std;const int N=500+5;int n,m,k,mx,num,sum,ass,tot,a[N][N],b[N][N],c[N][N],d[N*N],ans[N*N],dx[4]={-1,0,0,1},dy[4]={0,-1,1,0},vis[N][N];struct giao{int x,y,id;
}q[N*N];bool cmp(giao x,giao y){return (d[c[x.x][x.y]]>=k)<(d[c[y.x][y.y]]>=k);
}void work(int rx,int ry,int z,int id){queue<int> qx,qy;qx.push(rx),qy.push(ry);vis[rx][ry]=tot;int res=0;while(!qx.empty()){int x=qx.front(),y=qy.front();qx.pop(),qy.pop();c[x][y]=id;res++;for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx<1||ny<1||nx>n||ny>m||vis[nx][ny]==tot) continue;if(abs(a[nx][ny]-a[x][y])>z) continue;qx.push(nx),qy.push(ny);vis[nx][ny]=tot;}}d[id]=res;
}void solve(int l,int r,int a,int b){tot++;if(a>b) return;if(l==r){for(int i=a;i<=b;i++)ans[q[i].id]=l;return;}memset(vis,0,sizeof(vis));int mid=l+r>>1;for(int i=a;i<=b;i++)if(vis[q[i].x][q[i].y]!=tot){sum++;work(q[i].x,q[i].y,mid,sum);}sort(q+a,q+b+1,cmp);for(int i=a;i<=b;i++)if(d[c[q[i].x][q[i].y]]>=k){solve(l,mid,i,b);solve(mid+1,r,a,i-1);return;}solve(mid+1,r,a,b);
}int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);mx=max(mx,a[i][j]); }for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&b[i][j]);if(b[i][j]){num++;q[num]=(giao){i,j,num};b[i][j]=num;}}solve(0,mx,1,num);for(int i=1;i<=num;i++)ass+=ans[i];printf("%d",ass);return 0;
}

过了一周，我又想起了这道题，于是翻出来又看了看。发现脑子已经彻底被整体二分局限住了。遂看了一眼题解。看了5秒然后切了。

考虑直接枚举高度差，每枚举到一个值就把高度差等于这个值的两个点放进同一个联通块里，联通快打小大于 $T$ 时就可以统计答案。高度差最多只有 $2n$ 种，复杂度可以接受。

为了方便统计两点之间高度差一开始先在相邻点之间连边。最后用一个并查集即可。

复杂度应该是 $O(n^2)$ 。

Code

#include<bits/stdc++.h>
using namespace std;const int N=500+5;
typedef long long ll;int n,m,k,cnt,siz[N*N],f[N*N],a[N][N],b[N][N];
ll ans;
vector<int> v[N*N];struct giao{int x,y,v;
}e[N*N*2];bool cmp(giao x,giao y){return x.v<y.v;
}int find(int x){return x==f[x]?x:f[x]=find(f[x]);
}int id(int x,int y){return (x-1)*m+y;
}int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);v[id(i,j)].push_back(id(i,j));f[id(i,j)]=id(i,j);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&b[i][j]);siz[id(i,j)]=b[i][j];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(i!=n) e[++cnt]=(giao){id(i,j),id(i+1,j),abs(a[i][j]-a[i+1][j])};if(j!=m) e[++cnt]=(giao){id(i,j),id(i,j+1),abs(a[i][j]-a[i][j+1])};}sort(e+1,e+1+cnt,cmp);for(int i=1,x,y;i<=cnt;i++){x=e[i].x,y=e[i].y;x=find(x),y=find(y);if(x==y) continue;if(v[x].size()>v[y].size()) swap(x,y);if(v[x].size()+v[y].size()>=k){if(v[x].size()<k) ans+=1ll*e[i].v*siz[x];if(v[y].size()<k) ans+=1ll*e[i].v*siz[y];}for(auto j:v[x])v[y].push_back(j);siz[y]+=siz[x];f[x]=y;}printf("%lld",ans);return 0;
}