CFGYM103104I-WHUPC I Sequence

题意：有个$n\times n,n\leq 5000$的矩阵，挖掉$m,m\leq 10^6$个格子，问不包括这些格子的子矩阵个数。

做法很容易考虑：枚举一行，这一行从左往右扫，依次计算每个格子为右下角的子矩阵个数。

扫的时候维护一个单调栈，里面存(元素，以这个元素为高度的格子最长向右延伸了多少格)

为什么要存第二个项呢？我们维护的单调栈里面，每个东西实际上表示的是一个矩形，含义是：在我们处理完当前这个列后，这些矩形里的元素都可以作为合法的子矩阵左上顶点。

扫的时候维护一个东西：单调栈里所有矩形的大小和$sum$，即合法的左上顶点个数。

每次加入一个元素$x$，分以下三种情况讨论：

• $x$大于单调栈最后的元素：直接加入。长度记为1，sum加上$x$(显然多了这么多合法的格子)
• $x$等于单调栈最后的元素：单调栈最后的元素的长度加1，sum加上$x$
• $x$小于单调栈最后的元素：弹出单调栈最后的元素，并把其长度加到倒数第二个元素上，然后重复这三个check

最后我们每插入一个元素后，所维护的sum就是以这个点为右下角的答案。

另外有一个坑：输入1625 0，答案输出正确，但是从1626 0开始，答案越来越小，看起来像是溢出了，但是开-fsanitize=undefined没报任何问题，结果最后查出来了，算一行的答案时使用的是std::accumlate，初始值传的是int类型，而后累加变量自动推导为int，导致这个函数里面溢出了，然后由于ubsan并不会对包含的其他文件的代码做检查，于是挂掉了。

#include <assert.h>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using int_t = long long;
using std::cin;
using std::cout;
using std::endl;
/**
 * 1624 0 -> R
 * 1625 0 -> R
 * 1626 0 -> E 正确1749670208001 本程序 1736785306113
 * 1627 0 -> E
 */
bool block[5001][5001];
int_t upmost[5001][5001];
int_t n, m;
int main() {
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int_t i = 1; i <= m; i++) {
        int_t r, c;
        cin >> r >> c;
        block[r][c] = true;
    }
    for (int_t i = 1; i <= n; i++) {  //列
        int_t lastpos = 0;
        for (int_t j = 1; j <= n; j++) {
#ifdef DEBUG
            // cout << "block " << j << " " << i << " = " << block[j][i] <<
            // endl;
#endif
            if (block[j][i])
                lastpos = j;
            upmost[j][i] = lastpos;
#ifdef DEBUG
            cout << "upmost " << j << " " << i << " = " << upmost[j][i] << endl;
#endif
        }
    }
    int_t result = 0;
    //枚举底边行号
    for (int_t i = 1; i <= n; i++) {
        static int_t answer[5001];  // j->以(i,j)为右下角的矩形个数
        //以当前元素为右下角的矩形个数
        int_t sum = 0;
        // first为元素，second为出现次数
        std::vector<std::pair<int_t, int_t>> stack;
        stack.emplace_back(0, 0);
        for (int_t j = 1; j <= n; j++) {
            int_t x = i - upmost[i][j];  //向上延伸的空格子数(包括i,j)
            int_t count = 1;
            while (x < stack.back().first) {
                count += stack.back().second;
                sum -= stack.back().first * stack.back().second;
                stack.pop_back();
            }
            assert(sum >= 0);
            if (x == stack.back().first) {
                stack.back().second += count;
            } else {
                stack.emplace_back(x, count);
            }
            sum += x * count;
            answer[j] = sum;
            // cout << "answer col " << j << " = " << answer[j] << endl;
#ifdef DEBUG
            cout << "pushed col " << j << " val " << x << " sum = " << sum
                 << " answer = " << answer[j] << endl;
#endif
        }
        int_t currrow = std::accumulate(answer + 1, answer + 1 + n, (int_t)0);
        result += currrow;
        // cout << "answer row " << i << " = " << currrow << " " << currrow / i
        //      << " " << currrow % i << endl;
#ifdef DEBUG
        cout << "answer row " << i << " = " << currrow << endl;
#endif
    }
    cout << result << endl;
    return 0;
}