题解 P5781 【[IOI2019]矩形区域】

· · 题解

题解

假设某个合法的矩形只有一行，是 a_{1,l}\sim a_{1,r}，那么显然有这样一个结论成立：a_{1,l-1} 是 a_{1,r+1} 左侧第一个大于它的 或者 a_{1,r+1} 是 a_{1,l-1} 右侧第一个大于它的

那么对于一个合法矩形，每一行都应该满足这个条件

每一列应该也要满足类似的条件

所以对于一行(或列)，可以通过单调栈来求出所有这样的 [l,r]

对于每一行都用这样的方法求出这样的 [l,r]，用一个vector: ok[l][r] 来存储所有 a_{i,l}~a_{i,r} 为合法段的 i

枚举矩形右边界 r，并每次更新 lok[u][d] 表示只考虑列的限制，当矩形的上下边界为u,d，右边界为r时，左边界最左是哪里

然后枚举矩形左边界 l，枚举 ok[l][r] 中的每一个连续段 [u,d]，那么矩形的上下边界在 [u,d] 中时一定是满足行的限制的，只需找出有多少个左右边界为 l,r，上下边界在 [u,d] 内的矩形满足条件即可

代码中做了注释

代码

#include <bits/stdc++.h>
#define N 2520
using namespace std;

template <typename T>
inline void read(T &num) {
    T x = 0, f = 1; char ch = getchar();
    for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
    for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
    num = x * f;     
}

int n, m, a[N][N], stk[N], cnt, top, ans; 
vector<int> ok[N][N]; //ok[l][r]: a[l][i]~a[r][i]为合法段的i的集合 
pair<int, int> tmp[N]; //临时存答案 
int lok[N][N], rok[N][N]; 

void solve(int *num, int len) { //找出所有合法段 
    cnt = top = 0;
    for (int i = 1; i <= len; i++) {
        while (top && num[i] > num[stk[top]]) {
            if (i > stk[top] + 1) tmp[++cnt] = make_pair(stk[top]+1, i-1); 
            //num[l] < num[r]
            top--;
        }
        if (top) {
            if (i > stk[top] + 1) tmp[++cnt] = make_pair(stk[top]+1, i-1);
            //num[l]>num[r]
            if (num[i] == num[stk[top]]) top--;
            //特殊处理相等情况 
        }
        stk[++top] = i; 
    }
}

void calc(int l, int r, int u, int d) { 
    //左右边界为l,r;上下边界在[u,d]内 
    int len = 0;
    for (int i = u - 1; i <= d + 1; i++) {
        a[0][++len] = a[i][r];
    }
    solve(a[0], len); //找出列的合法段 
    for (int i = 1; i <= cnt; i++) {
        int tl = tmp[i].first + u - 2, tr = tmp[i].second + u - 2;
        if (lok[tl][tr] <= l) ans++;
    }
} 

int main() {
    read(n); read(m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            read(a[i][j]);
        }
    }   
    for (int i = 2; i < n; i++) { //预处理ok集合 
        solve(a[i], m);
        for (int j = 1; j <= cnt; j++) ok[tmp[j].first][tmp[j].second].push_back(i); 
    }
    for (int r = 2; r < m; r++)  { //枚举矩形右边界 
        for (int i = 1; i <= n; i++) a[0][i] = a[i][r];
        solve(a[0], n);
        for (int i = 1; i <= cnt; i++) {
            if (rok[tmp[i].first][tmp[i].second] + 1 < r)
                lok[tmp[i].first][tmp[i].second] = r;
            rok[tmp[i].first][tmp[i].second] = r;
            //lok[u][d]表示只考虑列的限制，当矩形的上下边界为u,d，右边界为r时，左边界最左是哪里 
        } 
        for (int l = 2; l <= r; l++) { //枚举矩形左边界 
            if (!ok[l][r].size()) continue;
            int lst = ok[l][r][0];
            for (int i = 1; i < ok[l][r].size(); i++) {
                if (ok[l][r][i] > ok[l][r][i-1] + 1) {
                    //找出ok[l][r]中的一个连续段 
                    calc(l, r, lst, ok[l][r][i-1]);
                    lst = ok[l][r][i];
                }
            } 
            calc(l, r, lst, ok[l][r][ok[l][r].size()-1]);
        } 
    } 
    printf("%d\n", ans);
    return 0;
}