【题解】LuoGu6404：bob

原题传送门 一开始考虑到悬线法，但是我忘了，所以我就自己创新 假设我已经扣出了一个相同颜色的连通块 计算答案 对于第一列，答案贡献是$4\ast 1$ 第二列答案是$3\ast 1$ 第三列答案是$2\ast 2$ 第四列答案是$2\ast 1$

第一列答案是$2\ast 4$ 第二列答案是$2\ast 3$ 第三列答案是$3\ast 2$ 第四列答案是$4\ast 1$ 可以直接$O(n^2)$扫过来 对于每一列的点，用$upe{x}_j$维护往上扩展最远能到哪里 用单调栈维护上述过程

我还加了个离散化，现在才发现离散了个寂寞

Code：

#include <bits/stdc++.h> #define maxn 1010 #define LL long long using namespace std; struct data{ int val, id; }val[maxn * maxn]; int n, m, a[maxn][maxn]; LL tot[maxn], upex[maxn], cnt, sum, ans, stk[maxn]; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } int id(int x, int y){ return (x - 1) * m + y; } bool cmp(data x, data y){ return x.val < y.val; } int main(){ freopen("bob.in", "r", stdin); freopen("bob.out", "w", stdout); n = read(), m = read(); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j){ int Id = id(i, j); val[Id].val = read(), val[Id].id = Id; } sort(val + 1, val + n * m + 1, cmp); int p = 0; val[0].val = val[1].val - 1; for (int i = 1; i <= n * m; ++i){ if (val[i].val != val[i - 1].val) ++p; int Id = val[i].id, x = (Id - 1) / m + 1, y = (Id - 1) % m + 1; a[x][y] = p; } for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j){ if (a[i - 1][j] != a[i][j]) upex[j] = i; if (a[i][j] != a[i][j - 1] || j == 1){ sum = 0, cnt = 0; } int h = i - upex[j] + 1, newtot = 1; sum += h; while (cnt > 0 && stk[cnt] >= h) sum -= tot[cnt] * (stk[cnt] - h), newtot += tot[cnt], --cnt; stk[++cnt] = h, tot[cnt] = newtot; ans += sum; } printf("%lld\n", ans); return 0; }