1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #include <bits/stdc++.h>
#define lc ch[0][u]
#define rc ch[1][u]
using namespace std;
typedef long long ll;
const int N= 1010, M = 200010;
const int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int n, m, lb = 1, rb = 1;
int a[N][N], idx[M], idy[M];
int fa[M], ch[2][M], sta[M], top; bool rv[M];
int tr[M * 4], sum[M * 4], lz[M * 4], fst, snd;
ll ans = 1;
inline int Min(const int &x, const int &y) { return x < y ? x : y; }
inline bool nroot(int u) { return ch[0][fa[u]] == u || ch[1][fa[u]] == u; }
inline void Rev(int u) { rv[u] ^= 1, swap(lc, rc); }
inline void pd(int u) { if(rv[u]) Rev(lc), Rev(rc), rv[u] = 0; }
void rotate(int u) {
int y = fa[u], z = fa[y], k = ch[1][y] == u, w = ch[k ^ 1][u];
if(nroot(y)) ch[ch[1][z] == y][z] = u; ch[k][y] = w, ch[k ^ 1][u] = y;
if(w) fa[w] = y; fa[u] = z, fa[y] = u;
}
void splay(int u) {
int y = u, z; for(sta[top = 1] = y; nroot(y); sta[++top] = y = fa[y]);
for(; top; pd(sta[top--]));
for(; nroot(u); rotate(u)) {
y = fa[u], z = fa[y];
if(nroot(y)) rotate((ch[0][y] == u) ^ (ch[0][z] == y) ? u : y);
}
}
inline void access(int u) {
for(int y = 0; u; u = fa[y = u]) splay(u), rc = y;
}
inline void makeroot(int u) { access(u), splay(u), Rev(u); }
inline void split(int x, int y) { makeroot(x), access(y), splay(y); }
inline int findroot(int u) {
access(u), splay(u); for(; lc; pd(u), u = lc); splay(u); return u;
}
inline void lnk(int x, int y) { makeroot(x), fa[x] = y; }
inline void cut(int x, int y) { split(x, y), fa[x] = ch[0][y] = 0; }
void pushup(int u) {
sum[u] = 0, tr[u] = Min(tr[u * 2], tr[u * 2 + 1]);
if(tr[u] == tr[u * 2]) sum[u] += sum[u * 2];
if(tr[u] == tr[u * 2 + 1]) sum[u] += sum[u * 2 + 1];
}
void pushdown(int u) {
if(!lz[u]) return ;
lz[u * 2] += lz[u], lz[u * 2 + 1] += lz[u];
tr[u * 2] += lz[u], tr[u * 2 + 1] += lz[u];
lz[u] = 0;
}
void build(int u, int l, int r) {
tr[u] = 0, sum[u] = r - l + 1; if(l >= r) return ;
int mid = (l + r) >> 1;
build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
}
void mdy(int u, int l, int r, int L, int R, int w) {
if(L <= l && r <= R) { tr[u] += w, lz[u] += w; return ; }
int mid = (l + r) >> 1; pushdown(u);
if(L <= mid) mdy(u * 2, l, mid, L, R, w);
if(R > mid) mdy(u * 2 + 1, mid + 1, r, L, R, w);
pushup(u);
}
void ask(int u, int l, int r, int L, int R) {
if(L <= l && r <= R) {
if(fst > tr[u]) fst = tr[u], snd = 0; if(fst == tr[u]) snd += sum[u];
return ;
}
int mid = (l + r) >> 1; pushdown(u);
if(L <= mid) ask(u * 2, l, mid, L, R);
if(R > mid) ask(u * 2 + 1, mid + 1, r, L, R);
}
bool check() {
static int tmp[5]; int len = 0;
for(int i = 0; i < 4; i++) {
int x = idx[rb + 1] + dir[i][0], y = idy[rb + 1] + dir[i][1];
if(!x || !y || x > n || y > m || a[x][y] < lb || a[x][y] > rb)
continue;
tmp[++len] = findroot(a[x][y]);
}
sort(tmp + 1, tmp + len + 1);
for(int i = 1; i < len; i++) if(tmp[i] == tmp[i + 1]) return 0;
return 1;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)
scanf("%d", &a[i][j]), idx[a[i][j]] = i, idy[a[i][j]] = j;
build(1, 1, n * m), mdy(1, 1, n * m, 1, 1, 1);
for(; rb < n * m;) {
for(; lb < rb && !check(); ++lb) for(int i = 0; i < 4; i++) {
int x = idx[lb] + dir[i][0], y = idy[lb] + dir[i][1];
if(!x || !y || x > n || y > m || a[x][y] < lb || a[x][y] > rb)
continue;
cut(lb, a[x][y]);
}
++rb, mdy(1, 1, n * m, lb, rb, 1);
for(int i = 0; i < 4; i++) {
int x = idx[rb] + dir[i][0], y = idy[rb] + dir[i][1];
if(!x || !y || x > n || y > m || a[x][y] < lb || a[x][y] > rb)
continue;
lnk(rb, a[x][y]), mdy(1, 1, n * m, lb, a[x][y], -1);
}
fst = M, snd = 0, ask(1, 1, n * m, lb, rb); if(fst == 1) ans += snd;
}
printf("%I64d\n", ans);
return 0;
}
|