小a的轰炸游戏（差分，前缀和）

题目传送门

题意：

给出一个n*m的矩形，然后有两个操作.

1操作，对一个给出的菱形，对菱形范围内的东西进行+1。

2操作，对一个上半菱形的区域，进行+1操作。

最后求矩形内各个数的异或和。

思路：

在矩形中，我们在四个角上进行++--，然后利用差分的性质，就解决了区间更新，

但是在这里，想破脑汁，也没想出怎么进行++--。因为矩形的差分是横着或者竖着的，

最后的求和非常容易，但是这里不一样。最后看了题解豁然大悟，原来差分还可以动态的来，

本行的差分数组使用完了，还可以把差分数组下传，继续在下一层继续起到作用，这是神奇的操作。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 3005

#define L 1000

int n,m,q;

int a[N][N],b[N][N],c[N][N],d[N][N];

int bb[N][N];

void up(int x,int y,int l)

{

    a[x-l/][y]++;a[x+][y-l/-]--;

    b[x-l/][y+]--;b[x+][y+l/+]++;

}

void down(int x,int y,int l)

{

    c[x+][y-l/+]++;c[x+l/+][y+]--;

    d[x+][y+l/]--;d[x+l/+][y]++;

}

int main()

{

    while(~scanf("%d %d %d",&n,&m,&q))

    {

        /*memset(a,0,sizeof(a));

        memset(b,0,sizeof(a));

        memset(c,0,sizeof(a));

        memset(d,0,sizeof(a));*/

        while(q--)

        {

            int op;

            int x,y,l;

            scanf("%d %d %d %d",&op,&x,&y,&l);

            x+=L,y+=L;

            up(x,y,l);

            if(op==) down(x,y,l);

        }

        int ans=;

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

       {

           int cnt=;

           for(int j=;j<m+*L;j++)

           {

               cnt+=a[i][j]+b[i][j]+c[i][j]+d[i][j];

               if(i>=L+&&i<=L+n&&j>=L+&&j<=m+L){

               ans^=cnt;//bb[i-L][j-L]=cnt;

               }

               a[i+][j-]+=a[i][j];

               b[i+][j+]+=b[i][j];

               c[i+][j+]+=c[i][j];

               d[i+][j-]+=d[i][j];

           }

       }

     /*  for(int i=1;i<=n;i++)

       {

           for(int j=1;j<=m;j++)

           {

               cout<<bb[i][j]<<" ";

           }

           cout<<endl;

       }*/

       printf("%d\n",ans);

    }

    return ;

}

参考：https://blog.csdn.net/qq_41289920/article/details/86683583

巴特西

小a的轰炸游戏（差分，前缀和）

最新文章

热门文章