题解【[USACO15FEB]Cow Hopscotch G】

很久以前就用线段树过了这题，现在刚学了cdq又用cdq写了一遍这题，所以就把两种做法都讲一下。

以下的 $n$ 指 $R$，$m$ 指 $C$​。

朴素做法

一眼的递推，$f_{i,j}$ 表示走到格子 $(i,j)$ 的方案数，$a_{i,j}$ 为格子 $(i,j)$ 的标号。

$$f_{i,j}=\sum f_{x,y}(x<i,y<j,a_{i,j}\ne a_{x,y})$$

时间复杂度 $O(n^2m^2)$，需要优化。

线段树

建 $nm$ 棵线段树，第 $k$ 棵线段树维护 $a_{i,j}=k$ 的 $f_{i,j}$ 值。我们从小到大枚举行号，这样就不用考虑行的限制。

若当前计算到了 $i$ 行，第 $0$ 棵线段树维护了如下的序列：

$$\sum\limits^i_{x=1}f_{x,1},\sum\limits^i_{x=1}f_{x,2}... \sum\limits^i_{x=1}f_{x,m}$$

第 $k$ 棵线段树维护了如下的序列：

$$\sum\limits^i_{x=1}f_{x,1}(a_{x,1}=k),\sum\limits^i_{x=1}f_{x,2}(a_{x,2}=k)... \sum\limits^i_{x=1}f_{x,m}(a_{x,m}=k)$$

计算第 $i$ 行时，每个 $f_{i,j}$ 的答案即为第 $0$ 棵线段树中区间 $[1,j-1]$ 的和减去第 $a_{i,j}$ 棵线段树区间 $[1,j-1]$ 的和。

线段树要动态开点，时间复杂度 $O(nm\log m)$​。

#include <cstdio>
#define GetL(x) (ls[x] ? ls[x] : ls[x] = ++ tot)
#define GetR(x) (rs[x] ? rs[x] : rs[x] = ++ tot)

const int MX = 20000005, MOD = 1e9 + 7;
int sum[MX], ls[MX], rs[MX], tot, dp[755][755], v[755][755];
void update(const int O, const int l, const int r, const int x, const int d) {
	if (l == r) {sum[O] = (sum[O] + d) % MOD; return;}
	const int mid(l + r >> 1);
	if (x <= mid) update(GetL(O), l, mid, x, d);
	else update(GetR(O), mid + 1, r, x, d);
	sum[O] += d, sum[O] %= MOD;
}
int query(const int O, const int l, const int r, const int L, const int R) {
	if (L <= l && r <= R) return sum[O];
	int ans(0), mid(l + r >> 1);
	if (ls[O] && L <= mid) ans = query(ls[O], l, mid, L, R);
	if (rs[O] && mid < R) ans = (ans + query(rs[O], mid + 1, r, L, R)) % MOD;
	return ans;
}

int main() {
	int R, C, K;
	scanf("%d%d%d", &R, &C, &K);
	for (int i(1); i <= R; ++ i)
	for (int j(1); j <= C; ++ j)
		scanf("%d", &v[i][j]);
	tot = K;
	update(v[1][1], 1, C, 1, dp[1][1] = 1);
	update(0, 1, C, 1, 1);
	for (int i(2); i <= R; ++ i) {
		for (int j(1); j <= C; ++ j)
			dp[i][j] = (query(0, 1, C, 1, j - 1) - query(v[i][j], 1, C, 1, j - 1)) % MOD;
		for (int j(1); j <= C; ++ j) 
			update(v[i][j], 1, C, j, dp[i][j]), update(0, 1, C, j, dp[i][j]);
	}
	printf("%d", (dp[R][C] + MOD) % MOD);
	return 0;
}

CDQ分治

观察那个 $(x<i,y<j,a_{i,j}\ne a_{x,y})$，除去最后那一个不等于的限制，这不就一个三维偏序嘛。

cdq分治的时候 $i$ 这一维天然有序，$j$ 这一维 cdq 分治削掉，$a_{i,j}$ 那维是树状数组维护，所以即使是不等号也没关系。

cdq分治里 $g_k$ 表示目前区间内所有 $a_{i,j}=k$ 的 $f_{i,j}$ 总和，$g$ 的清空需要时间戳。

时间复杂度 $O(nm\log n)$​。

#include <cstdio>
#define int long long

const int mod = 1e9 + 7;
int f[755][755], tme[755 * 755], g[755 * 755], a[755][755], n, m, now;
void CDQ(int l, int r) {
	if (l == r) return;
	int mid = l + r >> 1, sum = 0;
	CDQ(l, mid), ++ now;
	for (int j = 1; j <= m; ++ j) {
		for (int i = mid + 1; i <= r; ++ i) {
			if (tme[a[i][j]] ^ now) tme[a[i][j]] = now, g[a[i][j]] = 0;
			f[i][j] = (f[i][j] + sum - g[a[i][j]]) % mod;
		}
		for (int i = l; i <= mid; ++ i) {
			if (tme[a[i][j]] ^ now) tme[a[i][j]] = now, g[a[i][j]] = 0;
			g[a[i][j]] = (g[a[i][j]] + f[i][j]) % mod, sum = (sum + f[i][j]) % mod;
		}
	}
	CDQ(mid + 1, r);
}
signed main() {
	scanf("%lld%lld%*d", &n, &m);
	for (int i = 1; i <= n; ++ i)
	for (int j = 1; j <= m; ++ j)
		scanf("%lld", &a[i][j]);
	f[1][1] = 1, CDQ(1, n);
	printf("%lld", (f[n][m] + mod) % mod);
	return 0;
}

做法对比

第一条结果为 cdq 分治，第二条为动态开点线段树。

可以看到，无论耗时，内存，码量，cdq全方位吊打线段树。