壹、关于题目 ?
题目背景
有一只 小香猪，它有一种奇怪的癖好 —— 它喜欢被尽可能多的人摸，当然，这个癖好其实也能够满足许多人的欲望。
现在，有一群共 \(Area=n\times m\) 个人站成一个矩阵，这个矩阵上坐标为 \((i,j)\) 的人有一个权值 \(a_{i,j}\)，如果 小香猪 想要走过一个大小为 \(r\times c\) 的矩阵，那么该矩阵需要满足极差恰好为 \(r\times c-1\). 当 小香猪 走过这个 \(r\times c\) 的子矩阵，显然地，它会被 \(r\times c\) 个人摸。由于 小香猪 被太多的人摸，它已经爽得神志不清，为了救助它，套套狗 需要求出它一共被摸过多少次（同一个人可以反复计算），但是该数很大，它只需要知道该数对 \(998244353\) 取模的结果。不过，即使是这样，套套狗 也会知道有多少人摸过 小香猪，因为它可以去询问 校长。
数据范围
对于 \(100\%\) 的数据，保证 \(Area\le 2\times 10^5\)，且 \(a_{i,j}\) 互不相同。
贰、关于题解 ?
据说是 \(\rm IOI2018-D1T2\) 的改编题？不过做法好像不大一样。
关键转化：一个矩阵满足条件，一定是这个区间内数字都是连续的，因为保证 \(a_{i,j}\) 互不相同。
考虑判定权值在区间 \([l,r]\) 内的所有数所在的格子是否形成了一个矩形，记这些格子的颜色为黑色，其它的格子颜色为白色。 考虑所有的 \((n + 1) × (m + 1)\) 个 \(2 × 2\) 的小正方形 (部分超出边界也算)，则所有黑色格子形成一个矩形，当且仅当恰好有 \(4\) 个小正方形内部有 \(1\) 个黑色格子， 并且没有任何一个小正方形内部有 \(3\) 个黑色格子。 从小到大枚举 \(r\)，对每个 \(l ≤ r\)，记 \(f(l)\) 表示染黑权值在 \([l,r]\) 内的格子后，有多少小正方形内部有 \(1\) 个或 \(3\) 个黑色格子。 可以发现有 \(f(l) ≥ 4, f(r) = 4\) ，于是只需要对每个 \(l\) 维护 \(f(l)\) 最小值，最小值的 数目和取得最小值的所有 \(l\) 之和。 每次 \(r\) 增加 \(1\) 时，会影响到周边的 \(4\) 个 \(2×2\) 的小正方形，在线段树上修改即可。 时间复杂度 \(\mathcal O(Area \log Area)\).
不过，如果算上代码实现，可能复杂度大概是 \(\mathcal O(Area\log^2 Area)\) 级别，稍微有点卡常。
叁、关于代码 ?
# pragma GCC optimize("Ofast")
# include <bits/stdc++.h>
using namespace std;
// # define USING_CSTDIO
# define NDEBUG
# include <cassert>
namespace Elaina {
# define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
# define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
# define fi first
# define se second
# define mp(a, b) make_pair(a, b)
# define Endl putchar(‘\n‘)
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
template <class T> inline T fab(T x) { return x < 0? -x: x; }
template <class T> inline void getmin(T& x, const T rhs) { x=min(x, rhs); }
template <class T> inline void getmax(T& x, const T rhs) { x=max(x, rhs); }
# ifndef USING_CSTDIO
inline char freaGET() {
# define BUFFERSIZE 5000
static char BUF[BUFFERSIZE], *p1=BUF, *p2=BUF;
return p1==p2 && (p2=(p1=BUF)+fread(BUF, 1, BUFFERSIZE, stdin), p1==p2)? EOF: *p1++;
# undef BUFFERSIZE
}
# define CHARGET freaGET()
# else
# define CHARGET getchar()
# endif
template <class T> inline T readin(T x) {
x=0; int f=0; char c;
while((c=CHARGET)<‘0‘ || ‘9‘<c) if(c==‘-‘) f=1;
for(x=(c^48); ‘0‘<=(c=CHARGET) && c<=‘9‘; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template <class T> inline void writc(T x, char s=‘\n‘) {
static int fwri_sta[55], fwri_ed=0;
if(x<0) putchar(‘-‘), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
} using namespace Elaina;
const int maxn=2e5;
const int inf=0x3f3f3f3f;
const int mod=998244353;
namespace saya {
int mn[maxn<<2|2], cnt[maxn<<2|2], tag[maxn<<2|2];
ll sum[maxn<<2|2];
# define ls (i<<1)
# define rs (i<<1|1)
# define mid ((l+r)>>1)
# define _lhs ls, l, mid
# define _rhs rs, mid+1, r
inline void pushup(int i) {
mn[i]=min(mn[ls], mn[rs]), cnt[i]=0, sum[i]=0;
if(mn[i]==mn[ls]) cnt[i]=cnt[ls], sum[i]=sum[ls];
if(mn[i]==mn[rs]) cnt[i]+=cnt[rs], sum[i]+=sum[rs];
}
inline void add(int i, int v) { mn[i]+=v, tag[i]+=v; }
inline void pushdown(int i) {
if(!tag[i]) return;
add(ls, tag[i]), add(rs, tag[i]), tag[i]=0;
}
void build(int i, int l, int r) {
tag[i]=0;
if(l==r) return mn[i]=inf, cnt[i]=1, sum[i]=l, void();
build(_lhs), build(_rhs), pushup(i);
}
void modify(int L, int R, int v, int i, int l, int r) {
if(L>R) return;
if(L<=l && r<=R) return add(i, v);
pushdown(i);
if(L<=mid) modify(L, R, v, _lhs);
if(mid<R) modify(L, R, v, _rhs);
pushup(i);
}
inline void clear(int p, int i, int l, int r) {
if(l==r) return mn[i]=0, void();
pushdown(i);
if(p<=mid) clear(p, _lhs); else clear(p, _rhs);
pushup(i);
}
# undef ls
# undef rs
# undef mid
# undef _lhs
# undef _rhs
} // using namespace saya;
int n, m, Area;
int posi[maxn+5];
// vector< vector<int> >a;
int **a;
inline void input() {
n=readin(1), m=readin(1), Area=n*m;
// a=vector< vector<int> >(n+5, vector<int>(m+5, 0));
a=new int*[n+5];
rep(i, 0, n+1) a[i]=new int[m+5];
rep(i, 0, n+1) rep(j, 0, m+1) a[i][j]=0;
rep(i, 1, n) rep(j, 1, m) {
a[i][j]=readin(1);
posi[a[i][j]]=(i-1)*m+j;
}
}
# define sign(i) ((i)&1? (-1): (1))
inline void change(int x, int y, int s) {
static int buc[5]={0};
buc[1]=a[x][y], buc[2]=a[x][y+1], buc[3]=a[x+1][y], buc[4]=a[x+1][y+1];
rep(i, 1, 4) rep(j, 1, 3) if(buc[j]>buc[j+1])
swap(buc[j], buc[j+1]);
int p=1; for(; buc[p]^s; ++p);
rep(i, 1, p) saya::modify(buc[i-1]+1, buc[i], sign(p-i), 1, 1, Area);
}
signed main() {
freopen("data.in", "r", stdin);
freopen("user.out", "w", stdout);
input();
saya::build(1, 1, Area);
ll ans=0;
rep(i, 1, Area) {
register int r=(posi[i]-1)/m+1, c=(posi[i]-1)%m+1;
saya::clear(i, 1, 1, Area);
rep(x, -1, 0) rep(y, -1, 0) change(r+x, c+y, i);
if(saya::mn[1]==4) ans+=1ll*saya::cnt[1]*(i+1)-1ll*saya::sum[1];
}
writc(ans%mod);
return 0;
}
肆、关键 の 地方 ?
主要是关键的地方 —— 合法矩阵内数字连续。
另外就是对刚好形成一个矩阵的刻画：当且仅当恰好有 \(4\) 个小正方形内部有 \(1\) 个黑色格子， 并且没有任何一个小正方形内部有 \(3\) 个黑色格子。