题解：P12019 [NOISG 2025 Finals] 洪水
Lucyna_Kushinada
·
·
题解
P12019 [NOISG 2025 Finals] 洪水
题意
给定一个 n\times m 的网格，每个格子有数字，第 i 行 j 列的为 a_{i,j}\in \{0,1\}，1 表示该格子为建筑格子，0 表示为空格子。
初始时在空格子 (x,y) 放水，然后会有如下淹没规律：
水不会流出边界。
记最终状态时被淹没的格子数为 f(x,y)。
求出 \displaystyle \sum_{i=1}^n \sum_{j=1}^m [a_{i,j}=0]f(i,j)。
## 题解
知识点：扫描线，线段树，单调栈，堆。
启发：
- 特定情况下使用堆实现延迟删除。
感觉全是基本功啊，可为什么前前后后搞了这么久呢。
一开始没用堆，用的 `multiset` 卡常卡了一天还没卡过去，很难受。
### 思考 0
- 空格子不会被淹没，当且仅当四联通域没有被淹没的。
- 建筑格子不会被淹没，当且仅当四联通域至多有一个被淹没的。
被淹没的格子外围，要么是边界，要么是建筑格子。
### 思考 1
想一想被淹没的格子组成的形状。
当淹没的格子外围有凸出时，凸出左右边包住的不会是边界，因为边界是平的，所以只能是建筑格子，而这也是不可能的，建筑格子显然也会被淹没，所以不存在凸出，同理，也不存在凹进。所以外围是平的。
可以得出重要结论：**被淹没的所有格子组成的图形一定是矩形**。而矩形外围一圈（不包括四个角斜向的）不是建筑格子就是边界。
考虑将边界全变为建筑格子，可以发现他们一定不会被淹没，所以可以等效。
那么矩形的上下左右边界就都是建筑格子。
### 思考 2
那么一个空格子的贡献就是包含它的最小矩形的面积。
考虑处理出所有矩形，在这之前，先思考其数量级，由于矩形内部一定不能存在一整行/列的建筑格子（不然就会变成两个矩形），一个矩形的任意两对边至多同时贡献到一个矩形，这个限制比较强，故其数量级大概是 $O(nm)$ 的。
处理出两个数组 $ha_{i,j},la_{i,j}$，分别表示如果 $(i,j)$ 是建筑格子，其向行/列增加方向最长的连续建筑格子的长度（包括自己）。
处理出所有矩形，可以先 $O(m)$ 枚举列 $y$ 为其左边界，然后在每一列里面枚举上下边界的 $x$ 坐标，判定能否组成矩形，如果能就加入，判定这一步会排除矩形内一整列建筑格子的情况。
当然，这里并不能 $O(n^2)$ 枚举，考虑两个 $i,j(i<j)$，如果 $la_{i,y}\le la_{j,y}$，则 $i$ 肯定无法和后面的搭配形成矩形了，倘若组成矩形，那么第 $j$ 行会其中形成一个一整行的建筑格子，所以肯定不合法。
这个过程可以用单调栈实现，时间复杂度 $O(n)$，这一步会排除矩形内一整行建筑格子的情况。
### 思考 3
根据之前得出的，一个空格子的贡献就是包含它的最小矩形的面积，考虑扫描线，对哪一维扫都可以，动态加入/删除矩形，权值是该矩形的面积。
一下讨论的是对 $y$ 坐标的扫描。
扫描线达到了一个消维的效果，那么问题就转变为了：
- 维护一个长度为 $n$ 的序列 $a$，初始时每个位置都为 $+\infty$，每次给出三元组 $(l,r,s)$，对每个 $i\in [l,r]$ 执行 $a_i\leftarrow \min(a_i,s)$，同时还需要支持随机撤销之前三元组 $(l,r,x)$ 的作用效果，单点询问 $a_i$ 当前的值。
第一眼有一个线段树的做法，每个节点维护一个 `multiset` 的做法。
区间赋值时，递归到完全被操作区间的包含的节点区间时将 $s$ 加入该节点的 `multiset`。
查询时，顺着查询位置走线段树上的节点直到走到叶子，答案就是路径上 `multiset` 里的最小值。
只可惜这个做法常数太大了，卡常卡了一页还没过，于是有一个常数更小更聪明的堆做法。
每个节点开一个 `pair<int,int>` 的 `priority_queue`，加入节点的形式是一个 `pair`，面积 $s$ 为 `first`，该矩形作用时间右端点为 `second`，查询时先不断弹出 `second` 小于当前扫描到的列的队头，然后取此时的队头。
此时优先队列里面可能还有超时的元素，为什么不弹呢？其实这里用到了延迟删除的思想，不弹它并不会影响答案，那就等到队头是他的时候再弹，因为时间是单调的，某个时刻超时了，那么后面所有时刻都是超时状态。
总时间复杂度 $O(nm \log^2 n)$，虽然和 `multiset` 做法的复杂度相同，但是常数小了不少。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define N 5005
#define ll long long
int n,m,ha[N][N],la[N][N];
int st[N],tp,a[N][N];
struct rec{
int l,r,s,ed;
};
vector<rec>ad[N];
inline void chk(int l,int r,int j){
if(r-l-1<=0||ha[l+1][j-1]<r-l-1){
return;
}
int i=j-1,ed=j+min(la[l][j],la[r][j])-1;
while(ha[l+1][i+1]<r-l-1&&i<=ed){
i++;
}
if(i>ed||i<j){
return;
}
// cout<<"suc\n";
ad[j].pb({l+1,r-1,(r-l-1)*(i-j+1),i});
// cout<<l+1<<' '<<r-1<<' '<<j<<' '<<i<<' '<<"\n";
}
struct segt{
#define mid ((l+r)>>1)
priority_queue<pr,vector<pr>,greater<pr>>q[N<<2];
inline void add(int L,int R,int k,int l,int r,int d,int ed){
if(L<=l&&R>=r){
q[k].push({d,ed});
return;
}
if(L<=mid){
add(L,R,k*2,l,mid,d,ed);
}
if(R>mid){
add(L,R,k*2+1,mid+1,r,d,ed);
}
}
inline int ask(int L,int k,int l,int r,int ed){
int ans=1e9;
while(1){
while(sz(q[k])&&q[k].top().se<ed){
q[k].pop();
}
if(sz(q[k])){
ans=min(ans,q[k].top().fi);
}
if(l==r){
break;
}
if(L<=mid){
r=mid;
k=k*2;
}
else{
l=mid+1;
k=k*2+1;
}
}
return ans;
}
#undef mid
}t;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
cin>>n>>m;
n+=2,m+=2;
rep(i,1,n){
a[i][1]=a[i][m]=1;
}
rep(i,1,m){
a[1][i]=a[n][i]=1;
}
#define getchar getchar_unlocked
char c=0;
rep(i,2,n-1){
rep(j,2,m-1){
c=getchar();
while(c!='0'&&c!='1'){
c=getchar();
}
a[i][j]=c-'0';
}
}
per(i,1,n){
per(j,1,m){
if(a[i][j]){
ha[i][j]=ha[i+1][j]+1;
la[i][j]=la[i][j+1]+1;
}
}
}
per(j,2,m-1){
tp=0;
rep(i,1,n){
while(tp){
chk(st[tp],i,j);
if(la[st[tp]][j]>la[i][j]){
break;
}
tp--;
}
st[++tp]=i;
}
}
ll ans=0;
rep(j,1,m){
for(rec u:ad[j]){
t.add(u.l,u.r,1,1,n,u.s,u.ed);
// cout<<j<<' '<<u.l<<' '<<u.r<<" add\n";
}
rep(i,1,n){
if(a[i][j]){
continue;
}
ans+=t.ask(i,1,1,n,j);
}
}
cout<<ans;
return 0;
}
```