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)\)。
\(n,m\le 5000\)。
题解
知识点：扫描线，线段树，单调栈，堆。
启发：
- 特定情况下使用堆实现延迟删除。
感觉全是基本功啊，可为什么前前后后搞了了这么久呢。
一开始没用堆，用的 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 做法的复杂度相同，但是常数小了不少。
#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 longint 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_unlockedchar 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;
}