1 条题解

  • 0
    @ 2025-8-24 22:07:41

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar tcl_tcl_tcl
    WA是一个人的狂欢

    搬运于2025-08-24 22:07:41，当前版本为作者最后更新于2020-03-15 10:34:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

    以下是正文

    蒟蒻的第一篇题解

    (update:二维数组区间修改模板中有地方有误，已更正) 一位题解重度依赖患者由于没有题解被迫营业的悲惨经历

    拿到题的的第一步当然是查看题解审题。相信在座的神犇们都已经看出来了，(我真的没有看算法标签)， 这题是一道树状数组的题，在刷完两道树状数组的模板题后，直接开始了强转一维树状数组的暴力解法，代码如下：

    #include <bits/stdc++.h>
using namespace std;
const int N = 2500;
const int K = 31;
int x0, Y0, x1, Y1;
int m, n, k;
int sum1[N*N + 1][K], sum2[N*N + 1][K];
char op;
int lowbit(int x) {
	return x & -x;
}
void update(int i, int ak, int bk) {
	int x = i;
	while (i <= n * n) {
		sum1[i][ak] += bk;
		sum2[i][ak] += (x - 1)*bk;
		i += lowbit(i);
	}
}
int getsum(int i, int k) {
	int x = i;
	int ans = 0;
	while (i != 0) {
		ans += (x * sum1[i][k] - sum2[i][k]);
		i -= lowbit(i);
	}
	return ans;
}
int main()
{
	cin >> n >> m;
	while (m--) {
		cin >> op;
		if (op == 'P') {
			cin >> x0 >> Y0 >> x1 >> Y1 >> k;
			while (k--) {
				int ak, bk;
				cin >> ak >> bk;
				if (bk & 1) {
					for (int y = Y0; y <= Y1; y++) {
						update(x0 + (y - 1) * n, ak, bk);
						update(x1 + (y - 1) * n + 1, ak, -bk);
					}
				}
			}
		}
		if (op == 'Q') {
			cin >> x0 >> Y0 >> x1 >> Y1;
			for (int i = 1; i <= 30; i++)
			{
				int sum = 0;
				for (int y = Y0; y <= Y1; y++) {
					sum += getsum(x1 + (y - 1) * n, i) - getsum(x0 + (y - 1) * n - 1, i);
				}
				cout << ((sum % 2) + 1);
			}
			cout << endl;
		}
	}
	return 0;
}

    结果当然是MLE+TLE大餐(其实三个点真香)，显然此题的正解不是 强转一维树状数组，而是二维树状数组，在分析开始我先介绍一下二维数组的三种题型以及对应的模板代码。

    二维树状数组

    1.单点修改+区间查询

    //while用for写也是一样的
void update(int x, int y, int z){
    int _y = y;
    while(x <= n){
        y = _y;
        while(y <= n)
            tree[x][y] += z, y += lowbit(y);
        x += lowbit(x);
    }
}
void query(int x, int y){
    int ans = 0, _y = y;
    while(x){
        y = _y;
        while(y)
            ans += tree[x][y], y -= lowbit(y);
        x -= lowbit(x);
    }
}

    2.区间修改+单点查询

    类似于一维的处理，可以设差分数组 d[i]=a[i][j]−a[i−1][j]+a[i][j−1]−a[i−1][j−1]d[i]=a[i][j]-a[i-1][j]+a[i][j-1]-a[i-1][j-1] 模板如下：

    //用万能头的选手不要使用x1,y1
void update(int x, int y, int z){ 
    int _y = y;
    while(x <= n){
        y = _y;
        while(y <= n)
            tree[x][y] += z, y += y & -y;
        x += x & -x;
    }
}
void range_update(int x1, int y1, int x2, int y2, int val){
    update(x1, y1, val);
    update(x1, y2 + 1, -val);
    update(x2 + 1, y1, -val);
    update(x2 + 1, y2 + 1, val);
}
void ask(int x, int y){
    int ans = 0, _y = y;
    while(x){
        y = _y;
        while(y)
            ans += tree[x][y], y -= lowbit(y);
        x -= lowbit(x);
    }
}

    3.区间修改+区间查询

    类比一维树状数组的区间修改查询，(x,y)的前缀和： $\sum_{i=1}^{x}\sum_{j=1}^{y}\sum_{k=1}^{i}\sum_{h=1}^{j}d[h][k]$ 其中,d[1][1]d[1][1]出现了x∗yx*y次,d[1][2]d[1][2]出现了x∗(y−1)x*(y-1)次 于是 $\sum_{i=1}^{x}\sum_{j=1}^{y}\sum_{k=1}^{i}\sum_{h=1}^{j}d[h][k]=\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]*(x+1-i)*(y+1-j)$ 展开得

    (x+1)∗(y+1)∗∑i=1x∑j=1yd[i][j](x+1)*(y+1)*\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j] −(y+1)∗∑i=1x∑j=1yd[i][j]∗i-(y+1)*\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]*i −(x+1)∗∑i=1x∑j=1yd[i][j]∗j-(x+1)*\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]*j +∑i=1x∑j=1yd[i][j]∗i∗j+\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]*i*j

    那么我们需要维护四个树状数组： d[i][j],d[i][j]∗i,d[i][j]∗j,d[i][j]∗i∗jd[i][j],d[i][j]*i,d[i][j]*j,d[i][j]*i*j

    代码模板如下：

    void update(int x, int y, int val) {
	for (int X = x; X <= n; X += lowbit(X))
		for (int Y = y; Y <= m; Y += lowbit(Y)) {
			t1[X][Y] += val;
			t2[X][Y] += val *x;
			t3[X][Y] += val * y;
			t4[X][Y] += val * x * y;
		}
}
void range_update(int xa, int ya, int xb, int yb, int val) { 
	update(xa, ya, val);
	update(xa, yb + 1, -val);
	update(xb + 1, ya, -val);
	update(xb + 1, yb + 1, val);
}
int query(int x, int y) {
	int res = 0;
	for (int i = x; i; i -= i & -i)
		for (int j = y; j; j -= j & -j)
			res += (x + 1) * (y + 1) * t1[i][j]
			- (y + 1) * t2[i][j]
			- (x + 1) * t3[i][j]
			+ t4[i][j];
	return res;
}
int range_query(int xa, int ya, int xb, int yb) {
	return query(xb, yb) - query(xb, ya - 1) - query(xa - 1, yb) + query(xa - 1, ya - 1);
}

    题目分析

    很明显这道题属于以上分析的第三种题型区间修改+区间查询，套用模板可得以下代码：

    #include <bits/stdc++.h>
using namespace std;
const int N = 2500 + 1;
const int K = 31;
int t1[N][N][K], t2[N][N][K], t3[N][N][K], t4[N][N][K];	//第三个维度表示种类
int m, n, k;
int X1, Y1, X2, Y2;
int ak, bk;
char op;
int lowbit(int x)
{
	return x & -x;
}
void update(int x, int y, int k, int p)
{
	for (int X = x; X <= n; X += lowbit(X))
		for (int Y = y; Y <= n; Y += lowbit(Y)) {
			t1[X][Y][k] += p;
			t2[X][Y][k] += p * x;
			t3[X][Y][k] += p * y;
			t4[X][Y][k] += p * x * y;
		}
}
void range_update(int xa, int ya, int xb, int yb, int k, int p)
{
	update(xa, ya, k, p);
	update(xa, yb + 1, k ,-p);
	update(xb + 1, ya, k, -p);
	update(xb + 1, yb + 1, k, p);
}
int query(int x, int y, int k)
{
	int ans = 0;
	for (int i = x; i; i -= lowbit(i))
		for (int j = y; j; j -= lowbit(j))
			ans += (x + 1)*(y + 1)*t1[i][j][k]
			- (y + 1)*t2[i][j][k]
			- (x + 1)*t3[i][j][k]
			+ t4[i][j][k];
	return ans;
}
int range_query(int xa, int ya, int xb, int yb, int k)
{
	return query(xb, yb, k) - query(xb, ya - 1, k) - query(xa - 1, yb, k) + query(xa - 1, ya - 1, k)  ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;
	while (m--) {
		cin >> op;
		if (op == 'P')
		{
			cin >> X1 >> Y1 >> X2 >> Y2 >> k;
			while (k--)
			{
				cin >> ak >> bk;
				range_update(X1, Y1, X2, Y2, ak, bk);
			}
		}
		if (op == 'Q')
		{
			cin >> X1 >> Y1 >> X2 >> Y2;
			for (int i = 1; i <= 30; i++)
				cout<<((range_query(X1, Y1, X2, Y2, i)%2)+1);
			cout << endl;
		}
	}
	return 0;
}

    很抱歉，这次30分也没有，本地会直接报错：LNK1248 映像大小(BA135000)超过允许的最大大小(80000000)，(~~通过查阅资料)~~仔细分析发现这和强转一维得到大小没有变化可能甚至还超过。观察到题目仅有最多30种物件，于是我们考虑状态压缩，用每一位表示物品奇偶性(0表示偶数个，1表示奇数个)，自然而然地就会想到异或运算。完整AC代码如下：

    #include <bits/stdc++.h>
using namespace std;
const int N = 2500 + 1;
const int K = 5;
unsigned int t1[N][N], t2[N][N], t3[N][N], t4[N][N];
int m, n, k;
int X1, Y1, X2, Y2;
int ak, bk;
unsigned int ans, val;
char op;
int lowbit(int x)
{
	return x & -x;
}
void update(int x, int y, unsigned int p)
{
	for (int X = x; X <= n; X += lowbit(X))
		for (int Y = y; Y <= n; Y += lowbit(Y)) {
			t1[X][Y] ^= p;
			t2[X][Y] ^= ((y) & 1) ? p : 0;	//如果(y-1)是偶数，乘以任何数也是偶数，对结果不影响
			t3[X][Y] ^= ((x) & 1) ? p : 0;
			t4[X][Y] ^= ((x)&(y) & 1) ? p : 0;
		}
}
void range_update(int xa, int ya, int xb, int yb, int p)
{
	update(xa, ya, p);
	update(xa, yb + 1 ,p);
	update(xb + 1, ya, p);
	update(xb + 1, yb + 1, p);
}
unsigned int query(int x , int y)
{
	unsigned int ans = 0;
	for (int i = x; i; i -= lowbit(i))
		for (int j = y; j; j -= lowbit(j))
			ans ^= (((x + 1)&(y + 1)&1)?t1[i][j]:0)^
			(((x + 1) & 1) ? t2[i][j] : 0) ^
			(((y + 1) & 1) ? t3[i][j] : 0) ^
			t4[i][j];
	return ans;
}
unsigned int range_query(int xa, int ya, int xb, int yb)
{
	return query(xb, yb) ^ query(xb, ya - 1) ^ query(xa - 1, yb) ^ query(xa - 1, ya - 1)  ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;
	while (m--) {
		cin >> op;
		if (op == 'P')
		{
			val = 0;
			cin >> X1 >> Y1 >> X2 >> Y2 >> k;
			while (k--)
			{
				cin >> ak >> bk;
				if (bk & 1)
					val ^= (1 << ak);//只有奇数个有更新的必要，偶数个不影响结果
			}
			range_update(X1, Y1, X2, Y2, val);
		}
		if (op == 'Q')
		{
			cin >> X1 >> Y1 >> X2 >> Y2;
			ans = range_query(X1, Y1, X2, Y2);
			for (int i = 1; i <= 30; i++)
			{
				ans = ans >> 1;
				if (ans & 1)
					cout << 2;
				else
					cout << 1;
			}
				cout << endl;
		}
	}
	return 0;
}

    看在我码的辛苦这是第一篇该题的详细题解的份上，各位大佬何不留个赞再走？

    • 1

    宝藏

    信息

    ID
    2492
    时间
    1000ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 22ms