XCPC wiki - 前缀和与差分 | 小明の雜貨鋪

/** 一维前缀和 **/
vector<ll> pre(n + 1);
for (int i = 0; i < n; i++) {
	pre[i + 1] = pre[i] + a[i];
}

// 查询[l, r)
auto get = [&](int l, int r) {
	return pre[r] - pre[l];
};


/** 二维前缀和 **/
vector s(m + 1, vector<ll>(n + 1));
for (int x = 0; x < m; x++) {
	for (int y = 0; y < n; y++) {
		s[x + 1][y + 1] = s[x + 1][y] + s[x][y + 1] - s[x][y] + a[x][y];
	}
}

// 查询(x1,y1)(含)-(x2,y2)(不含)
auto get = [&](int x1, int y1, int x2, int y2) {
	return s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1];
};


/** 三维前缀和 **/
vector s(m + 1, vector(n + 1, vector<ll>(p + 1)));
for (int x = 0; x < m; x++) {
    for (int y = 0; y < n; y++) {
        for (int z = 0; z < p; z++) {
            s[x + 1][y + 1][z + 1] = a[x][y][z]
              + s[x + 1][y + 1][z] + s[x + 1][y][z + 1] + s[x][y + 1][z + 1]
              - s[x + 1][y][z] - s[x][y + 1][z] - s[x][y][z + 1]
              + s[x][y][z];
        }
    }
}

// 查询(x1,y1,z1)(含)-(x2,y2,z2)(不含)的和
auto get = [&](int x1, int y1, int z1, int x2, int y2, int z2) {
    return s[x2][y2][z2]
         - s[x1][y2][z2] - s[x2][y1][z2] - s[x2][y2][z1]
         + s[x1][y1][z2] + s[x1][y2][z1] + s[x2][y1][z1]
         - s[x1][y1][z1];
};

CF2014D. Robert Hood and Mrs Hood

日期编号从 $1$ 到 $n$ ，在这期间来访者连续逗留 $d$ 天。罗宾总共计划了 $k$ 项工作。其中 $i$ 项工作发生在 $l_{i}$ 天和 $r_{i}$ 天之间。如果某项工作在 $d$ 天中的任何一天进行，那么这次访问就会与这项工作重叠。罗宾希望他弟弟的访问与最多的不同工作重叠，而他母亲的访问与最少的工作重叠。为罗宾的弟弟和母亲的访问寻找合适的开始日期。如果有多个合适的日期，输出择最早的一个。

int n, d, k;
cin >> n >> d >> k;

vector<int> L(n + 1), R(n + 1);
for (int i = 0; i < k; i++) {
	int l, r;
	cin >> l >> r;
	l--;
	L[l]++, R[r]++;
}
for (int i = 1; i <= n; i++) {
	R[i] += R[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
	L[i] += L[i + 1];
}

int mx = -1, mn = n + 1;
int imx = -1, imn = -1;
for (int i = 0; i <= n - d; i++) {
	int v = R[i] + L[i + d];
	if (v > mx) mx = v, imx = i + 1;
	if (v < mn) mn = v, imn = i + 1;
}
cout << imn << " " << imx << "\n";

经典差分问题：VJspr12E - 差分求区间和 (Tea Tasting)

题意有 $n$ 个人和 $n$ 杯茶，第 $i$ 个人每次会喝 $b_i$ 毫升的茶。第 $i$ 杯茶有 $a_i$ 毫升。总共会喝 $n$ 轮茶，第 $j$ 轮第 $i$ 个人会尝试喝第 $i+1-j$ 杯茶。喝的量为 $\min(a_{i+1-j},b_i)$ 毫升，并且使 $a_{i+1-j}$ 减少 $\min(a_{i+1-j},b_i)$ 。问 $n$ 轮后每个人喝了多少毫升茶。

思路考虑每杯茶对人的贡献。不难发现，第 $i$ 杯茶会对从第 $i$ 人开始的若干个人产生贡献。我们可以维护两个数组：

$cnt_i$ 表示对第 $i$ 人产生完整贡献的次数。
$ex_i$ 表示对第 $i$ 人产生的不完整贡献。

于是最终第 $i$ 人的答案就是 $cnt_i \times b_i + ex_i$ 。先求出 $a_i$ 的前缀和 $s_i$ 。对于每一杯茶，我们可以二分找到它的贡献终止的地方。设最后一个得到完整贡献的人下标为 $j$ ，则 $cnt_i$ 到 $cnt_j$ 整体加 $1$ 。 $ex_{j+1}$ 要加上剩余的茶 $a_i - (s_j - s_{i-1})$ 。由于 $cnt$ 只需区间加和一次查询，差分即可。

int a[N], b[N];
ll sum[N], cnt[N], ex[N];

void eachT() {
	int n = read();
	for (int i = 1; i <= n; i++) a[i] = read(), cnt[i] = ex[i] = 0;
	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (b[i] = read());

	for (int i = 1; i <= n; i++) {
		int r = lower_bound(sum + i, sum + n + 1, a[i] + sum[i - 1]) - sum - 1;
		cnt[i]++, cnt[r + 1]--;
		ex[r + 1] += a[i] - (sum[r] - sum[i - 1]);
	}  // [i,r]喝一次 剩下的给r+1

	for (int i = 1; i <= n; i++) {
		cnt[i] += cnt[i - 1];
		printf("%lld%c", cnt[i] * b[i] + ex[i], " \n"[i == n]);
	}
}

二维前缀和与差分模板

多次操作，每次给矩形上色，然后多次查询，问矩形是否全部上色。(VJwin1F - Monitor - UPSOLVE)

int n, m;
cin >> n >> m;

vector a(n + 1, vector<int>(m + 1)); // 多组数据需初始化

int q;
cin >> q;
while (q--) {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	x1--, y1--;
	a[x1][y1]++;
	a[x1][y2]--;
	a[x2][y1]--;
	a[x2][y2]++;
} // 差分预处理 现在 a[i][j]表示差分

vector s(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + a[i][j];
	}
} // 前缀和还原 现在 a[i][j]表示该点被上色的次数

a = vector(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		//cerr<<s[i][j]<<" \n"[j==m];
		if (s[i][j]) a[i - 1][j - 1] = 1;
	}
} // 上色的次数没有影响 一律改为1 便于判断 现在 a[i][j]表示该点是否被上色

s = vector(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + a[i][j];
	}
} // 前缀和 现在 a[i][j]表示该点左上角被染色的数量

cin >> q;
while (q--) {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	x1--, y1--;
	int s1 = s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1];
	int s2 = (x2 - x1) * (y2 - y1);
	cout << (s1 == s2 ? "YES" : "NO") << endl;
}

二维坐标一维化：2023 ICPC 南京 A. Cool, It’s Yesterday Four Times More

int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; i++) {
	cin >> s[i];
}

// 二维坐标一维化
auto change = [&](int x, int y) {
	return x * m + y;
};
auto get = [&](int p) {
	return pair(p / m, p % m);
};

DSU dsu(n * m);
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (s[i][j] == 'O') continue;
		if (i && s[i][j] == s[i - 1][j]) dsu.uno(change(i, j), change(i - 1, j));
		if (j && s[i][j] == s[i][j - 1]) dsu.uno(change(i, j), change(i, j - 1));
	}
}

vector<vector<int>> son(n * m);
for (int u = 0; u < n * m; u++) {
	son[dsu.find(u)].push_back(u);
}

int res = 0;
for (int u = 0; u < n * m; u++) {
	if (dsu.find(u) != u) continue;
	auto [x0, y0] = get(u);
	if (s[x0][y0] == 'O') continue;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			bool found = 1;
			for (auto v : son[u]) {
				auto [x, y] = get(v);
				auto [nx, ny] = pair(x + i - x0, y + j - y0);
				if (nx < 0 || nx >= n || ny < 0 || ny >= m || s[nx][ny] == 'O') {
					found = 0;
				}
			}
			cnt += found;
		}
	}
	if (cnt == 1) res += dsu.size(u);
}
cout << res << "\n";

2022 ICPC 南京 A. Stop, Yesterday Please No More

int n, m, k;
cin >> n >> m >> k;

string s;
cin >> s;

int x = 0, y = 0, D = 0, U = n, L = 0, R = m;
for (auto c : s) {
	if (c == 'D') y++;
	if (c == 'U') y--;
	if (c == 'L') x++;
	if (c == 'R') x--;
	D = max(D, y);
	U = min(U, n + y);
	L = max(L, x);
	R = min(R, m + x);
}

if (D >= U || L >= R) {
	cout << (k ? 0 : n * m) << '\n';
} else {
	k = (R - L) * (U - D) - k;  // died

	vector a(2 * m, vector<int>(2 * n));
	int x = m, y = n;
	a[x][y] = 1;
	for (auto c : s) {
		if (c == 'D') y++;
		if (c == 'U') y--;
		if (c == 'L') x++;
		if (c == 'R') x--;
		a[x][y] = 1;
	}

	// 二维前缀和
	vector s(2 * m + 1, vector<int>(2 * n + 1));
	for (int x = 0; x < 2 * m; ++x) {
		for (int y = 0; y < 2 * n; ++y) {
			s[x + 1][y + 1] = s[x + 1][y] + s[x][y + 1] - s[x][y] + a[x][y];
		}
	}
	auto get = [&](int x1, int y1, int x2, int y2) {
		return s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1];
	};

	int ans = 0;
	for (int x = 0; x < m; ++x) {
		for (int y = 0; y < n; ++y) {
			if (get(m - x + L, n - y + D, m - x + R, n - y + U) == k) {
				ans++;
			}
		}
	}
	cout << ans << '\n';
}

VJwin9C - Two TVs

题意给出一些线段的起点和终点，问能否用两个数轴装下这些线段，要求线段之间互不重叠。

思路用前缀和与差分处理，如果某段区间的线段数超过 2，则不行。为避免 $\mathbf{MLE}$ 有两种优化，一是离散化，二是开 std::map，然后只检查 a[i].second。

另有贪心做法：就两个数轴，按顺序放，能放一放一，不能放就放二。