[文章目录]
Description
方格纸与草稿纸一样，都是算法竞赛中不可或缺的重要工具。身经百战的小Q自然也会随身带着方格纸。小Q的方格纸有n行m列，一共n*m个方格，从上到下依次标记为第1,2,...,n行，从左到右依次标记为第1,2,...,m列，方便起见，小Q称第i行第j列的方格为(i,j)。小Q在方格纸中填满了数字，每个格子中都恰好有一个整数a(i,j)。小Q不喜欢手算，因此每当他不想计算时，他就会让你帮忙计算。小Q一共会给出q个询问，每次给定一个方格(x,y)和一个整数k(1<=k<=min(x,y))，你需要回答由(x,y),(x-k+1,y),(x,y-k+1)三个格子构成的三角形边上以及内部的所有格子的a的和。1<=n,m<=3000,1<=q<=3000000
维护两个前缀和，答案可以通过前缀和的容斥得到。
sx表示（i,j）,i=[1,x],j=[y,1]的三角形前缀和。
sj表示以该点为右下端点的矩形前缀和。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rint register unsigned int
using namespace std;
int n,m,q;
unsigned int f,A,B,C,a[3010][3010],ans;
unsigned int sj[3010][3010],sx[3100][3100],po[3000010];
inline unsigned int rng61(){
A ^= A << 16;
A ^= A >> 5;
A ^= A << 1;
unsigned int t = A;
A = B;
B = C;
C ^= t ^ A;
return C;
}
/*unsigned int work(unsigned int x,unsigned int y,unsigned int k)
{
unsigned int re=0,cnt=0;
for(int i=x-k+1;i<=x;i++)
{
cnt++;
for(int j=0;j<cnt;j++)
re+=a[i][y-j];
}
return re;
}*/
int main()
{
scanf("%d%d%d%u%u%u",&n,&m,&q,&A,&B,&C);
rint i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i][j]=rng61();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
sj[i][j]=sj[i-1][j]+sj[i][j-1]-sj[i-1][j-1]+a[i][j];
sx[i][j]=sx[i-1][j+1]+sj[i][j]-sj[i][j-1];
}
rint x,y,k; po[q]=1;
for(i=q-1;i>0;i--) po[i]=po[i+1]*233;
for(i=1;i<=q;i++)
{
x=rng61()%n+1;
y=rng61()%m+1;
k=rng61()%min(x,y)+1;
f=(sj[x][y]+sx[(x-k-1)>0?x-k-1:0][y+1]-sx[x-1][y-k+1]-sj[x][y-k]);
ans=ans+po[i]*f;
}
printf("%u",ans);
}