异或（xor）
每次所加三角形的范围如图所示：
这道题做法较多，我是通过两组差分与前缀和来做的。
首先需要一个三角形差分，使每一次在差分数组中修改时，影响到的范围是一个三角形，比如这样（红色点为 \((x,y)\)，即 \((r,c)\)）：
假设我们真正需要修改的三角形是橙色部分：
那么联系到正常差分，很容易想到在 \((x+l,y+l)\) 的位置减去多出的值：
然而，左下方还多出了一块矩形，而这不是我们想要的，所以我们可以再额外维护一个矩形的二维差分来抵消这部分多出的贡献（像正常二维差分一样在这块矩形区域内全部减去多出的贡献即可）：
最后，对所有差分数组求前缀和，矩形差分数组的前缀和很好求，而三角形差分数组的前缀和则要额外注意。根据差分数组影响的三角形范围倒推可以得知，深蓝色部分的三角前缀和应该是这一部分的和：
其中深蓝色块的三角前缀和等于紫色块的三角前缀和加上深灰色部分，即（\(sum\) 表示三角前缀和，\(dif\) 表示差分数组）：
\[sum_{i,j}=sum_{i-1,j-1}+\sum_{k=1}^{i-1}dif_{k,j} \]然后就做出来了，时间复杂度 \(O(N^2)\)：
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1005;
int n,q;
LL tr_dif[N][N],sq_dif[N][N];
LL tr_sum[N][N],sq_sum[N][N];
//triangle, square
inline void Add(int x,int y,int l,int s)
{
tr_dif[x][y]+=s;
if(x+l<=n&&y+l<=n) tr_dif[x+l][y+l]-=s;
if(x+l<=n) sq_dif[x+l][y]-=s;
if(x+l<=n&&y+l<=n) sq_dif[x+l][y+l]+=s;
return;
}
void Calc_sum()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
sq_sum[i][j]=sq_dif[i][j]+sq_sum[i-1][j]+sq_sum[i][j-1]-sq_sum[i-1][j-1];
for(int j=1;j<=n;j++)
{
LL tmp=0;
for(int i=1;i<=n;i++)
{
tmp+=tr_dif[i][j];
tr_sum[i][j]=tr_sum[i-1][j-1]+tmp;
}
}
return;
}
int main()
{
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=1;i<=q;i++)
{
int x,y,l,s;
scanf("%d%d%d%d",&x,&y,&l,&s);
Add(x,y,l,s);
}
Calc_sum();
LL ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans^=tr_sum[i][j]+sq_sum[i][j];
printf("%lld\n",ans);
return 0;
}
对于每一行维护一个差分的做法时间复杂度是 \(O(QN)\) 的，似乎也可以卡一卡。