雅礼NOIP2018集训 day3 u

雅礼NOIP2018集训 day3 u

题面

考虑一个\(n*n\)的矩阵\(A\)，初始所有元素均为\(0\)。执行\(q\)次如下形式的操作：给定\(4\)个整数\(r,c,l,s\)，对于每个满足\(x\in[r,r+l),y\in[c,xr+c]\)的元素\((x,y)\)，将权值增加\(s\)。也就是，给一个左上顶点为\((r,c)\)、直角边长为\(l\)的下三角区域加上\(s\)。 输出最终矩阵的元素异或和。

数据范围

\(1\leq n\leq10^3\)

大概思路

在A\((r,c)\)加上s 在A\((r+l,c)\)减去s 在B\((r,c+1)\)减去s 在B\((r+l,c+l+1)\)加上s

然后对A数组进行\(A[i,j]+=A[i-1,j]\)对B数组进行\(B[i,j]+=B[i-1,j-1]\)

最后每一排做一次前缀和