题解：P5152 宝藏

· · 题解

前置知识

二维树状数组

什么？你说你不会？没事，文末有讲解。

思路

因为只有 30 个物品，且只维护奇偶性，考虑压缩状态。

用二维树状数组维护即可。

具体来说，对于第 i 位，表示第 i 个物品个数是否是奇数（1 表示是奇数，0 表示是偶数）。

如果将每次修改看做 k 次修改，方式是显而易见的，每次在修改的位上异或即可。

而这样的话时间就爆炸了。

所以先将 k 次修改异或起来，再修改。

在树状数组方面也有一些不同（因为是异或么）。

对于维护 i \times P_{i,j} 的树状数组，要看 i 的奇偶性。j \times P_{i,j} 同理。

而 i \times j \times P_{i,j} 的树状数组要注意 i 和 j 的奇偶性。

然后这题就结束了。

或许你会问了：为什么不用线段树或者树套树之类的呢？

因为空间太小了啊！

Code

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');
        }
    }
}

关于二维树状数组

首先你应该知道树状数组是什么吧……

二维树状数组与一维的思路类似，也是差分（以下以区间和为例）。

假设原数组叫 a_{i,j}。 令 P_{i,j} = a_{i,j} - a_{i-1,j} - a_{i,j-1} + a_{i-1,j-1}。

要求区间和，只需能求出 \sum_{i=1}^n \sum_{j=1}^m a_{i,j}。

令 Answer_{n,m} = \sum_{i=1}^n \sum_{j=1}^m a_{i,j}。

则 Answer_{n,m} = \sum_{i=1}^n \sum_{j=1}^m \sum_{k=1}^{i} \sum_{h=1}^{j} P_{k,h}。

考虑每个 P_{k,h} 共被算了多少次。

则 Answer_{n,m} = \sum_{i=1}^{n} \sum_{j=1}^m (n-i+1) \times (m-j+1) \times P_{i,j}。

即 Answer_{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}。

注意到 Answer_{n,m} 的取值与 P_{i,j},i \times P_{i,j},j \times P_{i,j},i \times j \times P_{i,j} 这四个东西有关，分别维护即可。

下面是二维树状数组的参考代码。

#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);
    }
};