单调栈求全1矩阵数量
<pre><code class="language-cpp">#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 5005;
vector<int> v;
int mp[maxn][maxn];
ll cnt[maxn][maxn];
int n, m;
ll ans = 0;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
mp[i][j] = 1;
}
}
for(int i = 1; i <= m; i++){
int a, b;
scanf("%d%d", &a, &b);
mp[a][b] = 0;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(mp[j][i] != 0) mp[j][i] = mp[j-1][i] + 1;
}
}
for(int i = 1; i <= n; i++){
v.clear();
for(int j = 1; j <= n; j++){
while(v.size() && mp[i][v.back()] > mp[i][j]) v.pop_back();
v.push_back(j);
if(v.size() > 1){
cnt[i][j] += cnt[i][v[v.size()-2]];
cnt[i][j] += 1ll * (j - v[v.size()-2]) * mp[i][j];
}else{
cnt[i][j] += 1ll * j * mp[i][j];
}
ans += cnt[i][j];
}
}
printf("%lld", ans);
}</code></pre>