专栏文章

题解：P5152 宝藏

wwwt100127
P5152题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipectia
此快照首次捕获于
2025/12/03 10:37
3 个月前
此快照最后确认于
2025/12/03 10:37
3 个月前
查看原文

前置知识

二维树状数组
什么？你说你不会？没事，文末有讲解。

思路

因为只有 3030 个物品，且只维护奇偶性，考虑压缩状态。
用二维树状数组维护即可。
具体来说，对于第 ii 位，表示第 ii 个物品个数是否是奇数（11 表示是奇数，00 表示是偶数）。
如果将每次修改看做 kk 次修改，方式是显而易见的，每次在修改的位上异或即可。
而这样的话时间就爆炸了。
所以先将 kk 次修改异或起来，再修改。
在树状数组方面也有一些不同（因为是异或么）。
对于维护 i×Pi,ji \times P_{i,j} 的树状数组，要看 ii 的奇偶性。j×Pi,jj \times P_{i,j} 同理。
而 i×j×Pi,ji \times j \times P_{i,j} 的树状数组要注意 ii 和 jj 的奇偶性。
然后这题就结束了。
或许你会问了：为什么不用线段树或者树套树之类的呢？
因为空间太小了啊！

Code

CPP
using UI=unsigned int;
const int N=2505;
int n,m;
struct BIT
{
	int tree[4][N][N];
	void ADD(int x,int y,UI k)
	{
		int i,j;
		for(i=x;i<=n;i+=lowbit(i))
		{
			for(j=y;j<=n;j+=lowbit(j))
			{
				tree[0][i][j]^=k;
				tree[1][i][j]^=((y&1)? k:0);//注意这里是y的奇偶性，后面同理
				tree[2][i][j]^=((x&1)? k:0);
				tree[3][i][j]^=((x&y&1)? k:0);
			}
		}
	}
	void update(int x,int y,int xx,int yy,int k)
	{
		ADD(x,y,k),ADD(xx+1,yy+1,k);
		ADD(xx+1,y,k),ADD(x,yy+1,k);
	}
	UI Qsum(int x,int y)
	{
		int i,j; UI ans=0;
		for(i=x;i;i-=lowbit(i))
		{
			for(j=y;j;j-=lowbit(j))
			{
				ans^=(((x+1)&(y+1)&1)? tree[0][i][j]:0);
				ans^=(((x+1)&1)? tree[1][i][j]:0);
				ans^=(((y+1)&1)? tree[2][i][j]:0);
				ans^=tree[3][i][j];
			}
		}
		return ans;
	}
	UI query(int x,int y,int xx,int yy)
	{
		return Qsum(x-1,y-1)^Qsum(xx,yy)^Qsum(xx,y-1)^Qsum(x-1,yy);
	}
}BIT;
void Memory_Love()
{
	int i,x,y,xx,yy,Num,u,v;
	UI k; char kind;
	read(n,m);
	while(m--)
	{
		kind=GetChar();
		read(x,y,xx,yy);
		if(kind=='P')
		{
			Num=read(),k=0;
			while(Num--)
			{
				read(u,v);
				if(v&1) k^=(1<<u);
			}
			BIT.update(x,y,xx,yy,k);
		}
		else
		{
			k=BIT.query(x,y,xx,yy);
			for(i=1;i<=30;i++)
			write((k>>i&1)+1);
			putchar('\n');
		}
	}
}

关于二维树状数组

首先你应该知道树状数组是什么吧……
二维树状数组与一维的思路类似，也是差分（以下以区间和为例）。
假设原数组叫 ai,ja_{i,j}。 令 Pi,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1P_{i,j} = a_{i,j} - a_{i-1,j} - a_{i,j-1} + a_{i-1,j-1}。
要求区间和，只需能求出 ∑i=1n∑j=1mai,j\sum_{i=1}^n \sum_{j=1}^m a_{i,j}。
令 Answern,m=∑i=1n∑j=1mai,jAnswer_{n,m} = \sum_{i=1}^n \sum_{j=1}^m a_{i,j}。
则 Answern,m=∑i=1n∑j=1m∑k=1i∑h=1jPk,hAnswer_{n,m} = \sum_{i=1}^n \sum_{j=1}^m \sum_{k=1}^{i} \sum_{h=1}^{j} P_{k,h}。
考虑每个 Pk,hP_{k,h} 共被算了多少次。
则 Answern,m=∑i=1n∑j=1m(n−i+1)×(m−j+1)×Pi,jAnswer_{n,m} = \sum_{i=1}^{n} \sum_{j=1}^m (n-i+1) \times (m-j+1) \times P_{i,j}。
即 Answern,m=∑i=1n∑j=1m(n+1)×(m+1)×Pi,j−(y+1)×i×Pi,j−(x+1)×j×Pi,j+i×j×Pi,jAnswer_{n,m} = \sum_{i=1}^{n} \sum_{j=1}^m (n+1) \times (m+1) \times P_{i,j} - (y+1) \times i \times P_{i,j} - (x+1) \times j \times P_{i,j} + i \times j \times P_{i,j}。
注意到 Answern,mAnswer_{n,m} 的取值与 Pi,j,i×Pi,j,j×Pi,j,i×j×Pi,jP_{i,j},i \times P_{i,j},j \times P_{i,j},i \times j \times P_{i,j} 这四个东西有关，分别维护即可。
下面是二维树状数组的参考代码。
CPP
#define lowbit(x) (x&-x)
struct BIT
{
	int tree[4][N][N];
	void ADD(int x,int y,int k)
	{
		int i,j;
		for(i=x;i<=n;i+=lowbit(x))
		{
			for(j=y;j<=m;j+=lowbit(j))
			{
				tree[0][i][j]+=k;
				tree[1][i][j]+=k*x;
				tree[2][i][j]+=k*y;
				tree[3][i][j]+=k*x*y;
			}
		}
	}
	void update(int x,int y,int xx,int yy,int k)
	{
		ADD(x,y,k);
		ADD(x,yy+1,-k);
		ADD(xx+1,y,-k);
		ADD(xx+1,yy+1,k);
	}
	int Qsum(int x,int y)
	{
		int i,j,ans=0;
		for(i=x;i;i-=lowbit(i))
		{
			for(j=y;j;j-=lowbit(j))
			{
				ans+=(x+1)*(y+1)*tree[0][i][j];
				ans-=(y+1)*tree[1][i][j];
				ans-=(x+1)*tree[2][i][j];
				ans+=tree[3][i][j];
			}
		}
		return ans;
	}
	int query(int x,int y,int xx,int yy)
	{
		return Qsum(xx,yy)-Qsum(x-1,yy)-Qsum(xx,y-1)+Qsum(x-1,y-1);
	}
};

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...