Silksong

冷却心 · 2025-08-25 13:11:08 · 题解

笑点解析：模拟赛赛时想完前面全部最后一步糖糖统计不会做赫赫，但是丝之歌要发售了好耶。

先考虑序列情况。相当于求出所有区间 [l,r] 满足 \max_{l\le i\le r} a_i < \min\{a_{l-1},a_{r+1}\}。我们可以两端 a_{l-1},a_{r+1} 中较小的一个，那么另一侧就是往左或右第一个大于等于他的位置，单调栈能简单 \mathcal O(n) 求出，于是发现一个性质：这样的区间只有 \mathcal O(n) 个。

放到网格上，先 \mathcal O(n^2) 求出若干个集合 S_{[l,r]} 表示合法区间有 [l,r] 的行集合，显然所有集合大小之和为 \mathcal O(n^2)。考虑统计答案，我们从左往右枚举合法矩形的右边界 r，同时维护若干指针 p_{[u,d]} 表示列方向上从第 r 列往前合法区间都有 [u,d] 的列的左端点最左的位置。具体维护方式考虑求出当前列的合法区间集合，不在该集合内的区间的 p 值赋值为 n+1 表示非法，在集合内的区间的 p 值和 r 取较小值，直接维护是 \mathcal O(n^2)，可以同时维护一个时间戳 t_{[l,r]} 表示上一次更新 [l,r] 的右边界，这样做到 \mathcal O(n) 更新 p 指针。然后枚举矩形左边界 l，那么合法矩形的上下边界 [u,d] 一定完全包含于集合 S_{[l,r]}，换言之，对于 S_{[l,r]} 内所有的极长连续段 [x,y]，他的贡献是所有 x\le a \le b \le y 中 p_{[a,b]} \le l 的个数，这样行列要求均已满足。具体实现我们在 p_{[a,b]} 的位置插入区间 [a,b] 那么从左往右枚举 l，就是每次对极长段 [l,r] 询问多少个 [a,b] 满足 l\le a\le b\le r，是一个二维数点，可以直接套 BIT 做完，但其实精细实现发现可以直接单调栈，原因是合法区间一定无交或包含，不会部分相交，所以直接单调栈统计。

视实现时间复杂度 \mathcal O(n^2 \log n) 或者 \mathcal O(n^2)，n,m 同阶。细节很少。

#include <bits/stdc++.h>
#define uint unsigned int
#define ull unsigned long long
#define LL long long
using namespace std;
const int N = 2.5e3 + 10;
int n, m, A[N][N], tmp[N]; LL Ans = 0;

int stk[N], tp;
void GetValidSegs(int* A, int n, vector<pair<int, int> >& res) {
    stk[tp = 1] = 1;
    for (int i = 2; i <= n; i ++) {
        while (tp && A[stk[tp]] < A[i]) tp --;
        if (tp && stk[tp] + 1 < i) res.push_back({stk[tp] + 1, i - 1});
        stk[++ tp] = i;
    }
    stk[tp = 1] = n;
    for (int i = n - 1; i >= 1; i --) {
        while (tp && A[stk[tp]] < A[i]) tp --;
        if (tp && stk[tp] - 1 > i && A[stk[tp]] != A[i]) res.push_back({i + 1, stk[tp] - 1});
        stk[++ tp] = i;
    } return ;
}

vector<int> col[N][N]; int lst[N][N], toki[N][N];
vector<pair<int, int> > ins[N]; vector<int> upd[N];

int tr[N], opt[N], len;
void add(int u, int k) { opt[++ len] = u; for (int i = u; i <= n; i += i & -i) tr[i] += k; }
int query(int u) { int r = 0; for (int i = u; i; i ^= i & -i) { r += tr[i]; } return r; }
void clear() {
    for (int i = 1; i <= len; i ++) for (int j = opt[i]; j <= n; j += j & -j) tr[j] = 0;
    len = 0; return ;
}

int main() {
    freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) cin >> A[i][j];
    for (int i = 1; i <= n; i ++) {
        vector<pair<int, int> > vec; GetValidSegs(A[i], m, vec);
        for (auto [l, r] : vec) col[l][r].push_back(i);
    } 
    for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) toki[i][j] = 250904;
    for (int i = 1; i <= m; i ++) {
        for (int j = 1; j <= n; j ++) tmp[j] = A[j][i];
        vector<pair<int, int> > vec; GetValidSegs(tmp, n, vec);
        for (auto [l, r] : vec) {   
            if (toki[l][r] != i - 1) lst[l][r] = i;
            toki[l][r] = i; ins[lst[l][r]].push_back({l, r});
        }
        for (int j = 1; j <= i; j ++) {
            for (auto [l, r] : ins[j]) upd[r].push_back(l);
            int lft = -1, lst = -1; 
            for (int k : col[j][i]) {
                if (lst != k - 1) {
                    if (lft != -1) Ans += query(n) - query(lft - 1);
                    lft = k;
                } lst = k; for (int x : upd[k]) add(x, 1);
            }
            if (lft != -1) Ans += query(n) - query(lft - 1);
            clear(); 
        }
        for (auto [l, r] : vec) ins[lst[l][r]].clear();
        for (int j = 1; j <= n; j ++) upd[j].clear();
    } cout << Ans << "\n";
    return 0;
}