牛客基础训练营 小a的轰炸游戏（二维差分）

小a的轰炸游戏
具体意思看题面

这题也太巧妙了
让我情不自禁想把它解释清楚
用图吧

这是一种想法，直接使用一维前缀和的思想，强行计算前缀和

但是想想，如果l是1000，5e5乘1000接受不了的哦

所以我们就想到用二维动态差分 只需要做8个操作，就是5e5乘8
完全可以

我们只标记8处

再用动态更新的方法，就可以达到第一张图的前缀和效果

具体怎么实现的呢

自己从代码里理解吧

    for(int i=0;i<n+2*L;i++)
    {
        int ans=0;
        for(int j=0;j<m+2*L;j++)
        {
            //前缀和
            ans+=a[i][j]+b[i][j]+c[i][j]+d[i][j];
            if(i>=L+1&&i<=L+n&&j>=L+1&&j<=L+m)res^=ans;
            //下传标记
            a[i+1][j-1]+=a[i][j];
            b[i+1][j+1]+=b[i][j];
            c[i+1][j+1]+=c[i][j];
            d[i+1][j-1]+=d[i][j];
        }
    }

至于为什么是从x至少要1000

因为防止越界

字数好像有点不够