区间元素替换与受限网格路径计数的算法解析
问题一：区间特定值替换
问题描述
给定一个长度为 $n$ 的数列 $a$，其中元素值域较小（$a_i \le 100$）。需要执行 $q$ 次操作，每次操作给定区间 $[l, r]$ 以及两个值 $x$ 和 $y$，要求将区间内所有等于 $x$ 的元素替换为 $y$。最终输出操作完成后的数列。
算法思路
由于数列元素的值域极小，直接采用线段树维护会面临较大的常数开销。此时，分块算法是一个更优的选择。
我们将数列划分为若干个大小约为 $\sqrt{n}$ 的块。对于每个块，维护一个映射数组 `tag`，其中 `tag[v]` 表示该块内原本值为 $v$ 的元素当前实际对应的值。
- 整块修改：当操作区间完全覆盖某个块时，只需遍历该块的 `tag` 数组（长度最大为 100），将所有等于 $x$ 的映射值修改为 $y$。时间复杂度为 $O(V)$，其中 $V$ 为值域大小。
- 零散块修改：当操作区间仅覆盖块的某一部分时，首先将该块的 `tag` 映射下传到实际数组中，并重置 `tag` 数组。然后暴力遍历区间内的元素进行替换。时间复杂度为 $O(\sqrt{n})$。
通过这种分块与值域映射结合的方式，可以高效地处理区间替换操作。
代码实现
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 200005;
const int MAXV = 105;
const int BLOCK_SIZE = 450;
int n, q;
int arr[MAXN];
int block_tag[MAXN / BLOCK_SIZE + 5][MAXV];
inline int get_block(int idx) {
return idx / BLOCK_SIZE;
}
inline void push_down(int b) {
int start = b * BLOCK_SIZE;
int end = min(n, start + BLOCK_SIZE - 1);
for (int i = start; i <= end; ++i) {
arr[i] = block_tag[b][arr[i]];
}
for (int v = 1; v < MAXV; ++v) {
block_tag[b][v] = v;
}
}
inline void update_range(int l, int r, int x, int y) {
if (x == y) return;
int bl = get_block(l);
int br = get_block(r);
if (bl == br) {
push_down(bl);
for (int i = l; i <= r; ++i) {
if (arr[i] == x) arr[i] = y;
}
} else {
push_down(bl);
int end_bl = (bl + 1) * BLOCK_SIZE - 1;
for (int i = l; i <= end_bl; ++i) {
if (arr[i] == x) arr[i] = y;
}
for (int b = bl + 1; b < br; ++b) {
for (int v = 1; v < MAXV; ++v) {
if (block_tag[b][v] == x) {
block_tag[b][v] = y;
}
}
}
push_down(br);
int start_br = br * BLOCK_SIZE;
for (int i = start_br; i <= r; ++i) {
if (arr[i] == x) arr[i] = y;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int num_blocks = get_block(n - 1) + 1;
for (int b = 0; b < num_blocks; ++b) {
for (int v = 1; v < MAXV; ++v) {
block_tag[b][v] = v;
}
}
cin >> q;
while (q--) {
int l, r, x, y;
cin >> l >> r >> x >> y;
l--; r--;
update_range(l, r, x, y);
}
for (int b = 0; b < num_blocks; ++b) {
push_down(b);
}
for (int i = 0; i < n; ++i) {
cout << arr[i] << (i == n - 1 ? "" : " ");
}
cout << "\n";
return 0;
}
问题二：带左下角禁区的网格路径计数
问题描述
在一个 $N \times M$ 的网格中，起点位于左上角 $(1,1)$，终点位于右下角 $(N,M)$。每次移动只能向右（$x$ 坐标加 1）或向下（$y$ 坐标加 1）。网格的左下角存在一个 $A \times B$ 的矩形禁区（即 $x \le A$ 且 $y \le B$ 的区域不可通行）。求从起点到终点的合法路径总数。
算法思路
在无限制的情况下，从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的格路数量可以通过组合数直接计算：$\binom{(x_2-x_1) + (y_2-y_1)}{x_2-x_1}$。
引入禁区限制后，由于移动方向仅限向右和向下，任何合法路径必然会在某个特定的纵坐标 $y$（其中 $y > B$）处穿过直线 $x = A$。我们可以利用这一几何特性，通过枚举路径穿过 $x = A$ 时的纵坐标 $y$ 来对路径进行分类。
对于每一个合法的穿越点 $(A, y)$（$y \in [B+1, M]$），路径可以被分为两段：
- 从起点 $(1,1)$ 到穿越点 $(A, y)$ 的路径数。
- 从穿越点 $(A, y)$ 到终点 $(N,M)$ 的路径数。
将这两段的路径数相乘，并对所有可能的 $y$ 值求和，即可得到最终的合法路径总数。这种方法避免了复杂的容斥原理，直接通过分类讨论将问题转化为简单的组合数求和。
代码实现
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 200005;
long long factorial[MAXN];
long long inverse_factorial[MAXN];
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
void precompute() {
factorial[0] = 1;
for (int i = 1; i < MAXN; ++i) {
factorial[i] = (factorial[i - 1] * i) % MOD;
}
inverse_factorial[MAXN - 1] = power(factorial[MAXN - 1], MOD - 2);
for (int i = MAXN - 2; i >= 0; --i) {
inverse_factorial[i] = (inverse_factorial[i + 1] * (i + 1)) % MOD;
}
}
long long nCr(int n, int r) {
if (r < 0 || r > n) return 0;
return factorial[n] * inverse_factorial[r] % MOD * inverse_factorial[n - r] % MOD;
}
long long countPaths(int x1, int y1, int x2, int y2) {
return nCr((x2 - x1) + (y2 - y1), x2 - x1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
precompute();
int N, M, A, B;
if (!(cin >> N >> M >> A >> B)) return 0;
long long total_paths = 0;
for (int y = B + 1; y <= M; ++y) {
long long paths_to_crossing = countPaths(1, 1, A, y);
long long paths_from_crossing = countPaths(A, y, N, M);
total_paths = (total_paths + paths_to_crossing * paths_from_crossing) % MOD;
}
cout << total_paths << "\n";
return 0;
}
