自动搬运

查看原文

来自洛谷，原作者为

	Dry_ice Я всегда буду любить мисс Tracy Reznik.

搬运于2025-08-24 21:56:00，当前版本为作者最后更新于2020-06-07 09:22:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本蒟蒻第四篇题解，上次提交写得太少了，这次望管理给过！

貌似是个树状数组模板题

写在前面

$Q$：树状数组是什么？

$A$：是一种数据结构。

定义原一维数组为 $A$ ，则树状数组 $C$ 的值为：

以此类推。

介绍一下著名的 $lowbit$ 函数吧。

lowbit

$Q$：$lowbit$ 求的是什么？

$A$：整数转为二进制后，最后一位 $1$ 及之后的所有 $0$ 所构成的数值。

$lowbit$ 看似麻烦，一看代码，发现也只有一行就解决了：

int lowbit(int x) {
	return x & -x;
}

这里涉及到了二进制补码的知识。

回到本题，你会豁然开朗！

思路

• 数据结构：树状数组
• 变化：多记一维 $color$
• 就没有其他改动了

CODE

#include <stdio.h>
int n, m;
int a[301][301];
int c[301][301][101];
inline void add(int x, int y, int k, int color) {
	for (int i = x; i <= n; i += i & -i)
		for (int j = y; j <= m; j += j & -j)
			c[i][j][color] += k;
}
inline int query(int x, int y, int color) {
	int ret = 0;
	for (int i = x; i; i -= i & -i)
		for (int j = y; j; j -= j & -j)
			ret += c[i][j][color];
	return ret;
}
int main(void) {
	scanf("%d %d", &n, &m);
	int Q, x1, y1, x2, y2, color;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &color);
			a[i][j] = color;
			add(i, j, 1, color);
		} 
	for (scanf("%d", &Q); Q--; ) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d %d %d", &x1, &y1, &color);
			add(x1, y1, -1, a[x1][y1]);
			a[x1][y1] = color;
			add(x1, y1, 1, color);
		}
		else {
			scanf("%d %d %d %d %d", &x1, &x2, &y1, &y2, &color);
			printf("%d\n", query(x2, y2, color) - query(x1 - 1, y2, color) - query(x2, y1 - 1, color) + query(x1 - 1, y1 - 1, color));
		}
	}
	return 0;
}

推荐树状数组题单

官方精选

• 【数据结构2-2】线段树与树状数组

用户分享

• 树状数组模板题

• CMの树状数组

The end. Thanks.

（走过路过一定要赞过啊