牛客网第二场Jfarm（随机化+二维前缀和）

链接：https://www.nowcoder.com/acm/contest/140/J

来源：牛客网

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  integers n,m,T(n*m<=,T<=)

For the next n lines, each line contains m integers in range[,n*m] denoting the type of plant in each grid.

For the next T lines, the i-th line contains  integers x1,y1,x2,y2,k(<=x1<=x2<=n,<=y1<=y2<=m,<=k<=n*m)

输出描述:

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

示例1

输入

复制

输出

复制

随机化，避免4=1+3=2+2

让他只有2+2；

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<vector>

using namespace std;

#define ll long long

int n,m,t;

int b[];

ll a[],qw;

vector<ll>g[];

int x,y,q,w,z;

int main()

{

    srand(time());

    scanf("%d%d%d",&n,&m,&t);

    for(int i=;i<=n+;i++)

        g[i].resize(m+);

    for(int i=;i<=n*m;i++)

    {

        a[i]=(ll)rand()*+(ll)rand();

        a[i]=a[i]+(ll)rand()*+(ll)rand();

    }

    for(int i=;i<=n*m;i++)

        scanf("%d",&b[i]);

    while(t--)

    {

        scanf("%d%d%d%d%d",&x,&y,&q,&w,&z);

        g[x][y]+=a[z];

        g[x][w+]-=a[z];

        g[q+][y]-=a[z];

        g[q+][w+]+=a[z];

    }

    int ans=;

    for(int i=;i<=n*m;i++)

    {

        x=i/m+;

        y=i%m;

        if(y==) y=m,x--;

        qw=g[x][y]+=g[x-][y]+g[x][y-]-g[x-][y-];

        if(qw%a[b[i]]) ans++;

    }

    printf("%d",ans);

    return ;

}