单调栈求全1矩阵数量

#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);
}