牛客多校第二场J.farm（二进制处理矩阵标记）

题目描述

White Rabbit has a rectangular farmland of n*m. In each of the grid there is a kind of plant. The plant in the j-th column of the i-th row belongs the a[i][j]-th type.
White Cloud wants to help White Rabbit fertilize plants, but the i-th plant can only adapt to the i-th fertilizer. If the j-th fertilizer is applied to the i-th plant (i!=j), the plant will immediately die.
Now White Cloud plans to apply fertilizers T times. In the i-th plan, White Cloud will use k[i]-th fertilizer to fertilize all the plants in a rectangle [x1[i]...x2[i]][y1[i]...y2[i]].
White rabbits wants to know how many plants would eventually die if they were to be fertilized according to the expected schedule of White Cloud.

输入描述:

The first line of input contains 3 integers n,m,T(n*m<=1000000,T<=1000000)
For the next n lines, each line contains m integers in range[1,n*m] denoting the type of plant in each grid.
For the next T lines, the i-th line contains 5 integers x1,y1,x2,y2,k(1<=x1<=x2<=n,1<=y1<=y2<=m,1<=k<=n*m)

输出描述:

Print an integer, denoting the number of plants which would die.

示例1

输入

复制

2 2 2
1 2
2 3
1 1 2 2 2
2 1 2 1 1

输出

复制

3

【题意】：

n*m的方格上，每个格子有个正整数（小于1e6）。然后给出T次矩形覆盖，每次给出一个矩形和一个数字，这个矩形内格子上的数字凡是不等于这个数字的格子，都会死掉。问最后会有多少个格子是死的？

【分析】二进制真有趣。。。

假如数字只有0和1，那我们可以用二维数组记录每个格子里是0还是1，然后每次覆盖的矩形，统计每个格子被覆盖了几次0和几次1（这个统计用前缀和和思想，应用到二维上，我的代码里是数组btree）。那么，扫描每个格子，如果是0且被覆盖了至少一次1，则这个格子死掉；或者这个格子是1，被覆盖了至少一次0，则这个格子死掉。

上面仅0和1的思路想明白，然后和有趣的二进制结合一下（二进制只有0和1）。两个数不相等的条件是二进制下，任意一位不相等即可。那我们可以把所有格子的数字和矩形覆盖的数据，全都在二进制下运算。对于每个格子，只要有一位死掉，那这个格子就死掉。也就是把大方格复制成了多个，每个只有0和1，按照上一段的思路即可

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=1e6+5;
int a[MAX],btree[2][MAX],die[MAX],n,m,Q;
int num[MAX],x1[MAX],x2[MAX],y11[MAX],y2[MAX]; //询问
int getid(int x,int y) //获得下标
{
    return (x-1)*m+y;
}
void addrect(int *c,int x1,int y1,int x2,int y2) //矩形标记
{
    c[getid(x1,y1)]++;
    if(y2<m)c[getid(x1,y2+1)]--;
    if(x2<n)c[getid(x2+1,y1)]--;
    if(x2<n&&y2<m)c[getid(x2+1,y2+1)]++;
}
void getpresum(int *arr) //处理为前缀和
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j>1)arr[getid(i,j)]+=arr[getid(i,j-1)];
            if(i>1)arr[getid(i,j)]+=arr[getid(i-1,j)];
            if(i>1&&j>1)arr[getid(i,j)]-=arr[getid(i-1,j-1)];
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=n*m;i++)
    {
        scanf("%d",&a[i]);
        btree[0][i]=btree[1][i]=die[i]=0;
    }
    for(int i=0;i<Q;i++)
        scanf("%d%d%d%d%d",&x1[i],&y11[i],&x2[i],&y2[i],&num[i]);
    for(int b=0;b<20;b++) //每一位
    {
        for(int i=0;i<Q;i++)
        {
            if(num[i]&1)
                addrect(btree[1],x1[i],y11[i],x2[i],y2[i]);
            else
                addrect(btree[0],x1[i],y11[i],x2[i],y2[i]);
            num[i]>>=1; //把下一次的位，移到最低位
        }
        getpresum(btree[0]);
        getpresum(btree[1]);
        for(int i=1;i<=n*m;i++) //统计,恢复
        {
            if(a[i]%2&&btree[0][i] || a[i]%2==0&&btree[1][i])
                die[i]=1;
            btree[0][i]=btree[1][i]=0;
            a[i]>>=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n*m;i++)ans+=die[i];
    cout<<ans<<endl;
    return 0;
}