u

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Wed Nov 07 16:05:56 CST 2018

In Category: NoCategory

Description：

一个 $n\times n$ 的矩阵 $A$ ，每次给左上顶点为 $(r,c)$ 、直角边长为 $l$ 的下三角区域加上 $s$ 。输出最终矩阵的元素异或和。

$1\leqslant n\leqslant 10^3$

Solution：

先处理最后求值显然可以差分，但是这个只能对每行差分，那么我们可以把差分数组差分，即先求一边前缀和得到差分数组，然后再求一边前缀和得到原矩阵。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

typedef long long ll;

inline ll rd()

{

	R ll res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,q;

#define MAXN 1010

ll c1[MAXN][MAXN];

ll c2[MAXN][MAXN];

ll m[MAXN][MAXN];

int main()

{

	freopen("u.in","r",stdin);

	freopen("u.out","w",stdout);

	scanf("%d%d",&n,&q);

	int x,y,l;

	ll s;

	for(int i = 1;i <= q;++i)

	{

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

		c1[x][y] += s;

		if(x + l <= n && y + l <= n)c1[x + l][y + l] -= s;

		c2[x + l][y] -= s;

		if(x + l <= n && y + l <= n)c2[x + l][y + l] += s;

	}

	ll ans = 0;

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

	{

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

		{

			c1[i][j] += c1[i - 1][j - 1];

			c2[i][j] += c2[i][j - 1];

			m[i][j] = m[i - 1][j] + c1[i][j] + c2[i][j];

			ans ^= m[i][j];

		}

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}

In tag: 技巧-差分

wjh15101051