题解 u

这里AC解法因为手残 tag2[min(r+l, n+1)][min(c+l+1, n+1)]+=s; 写成 tag2[min(r+l, n+1)][c+l+1]+=s; 惨遭RE，以后注意查边界，还有数组能开下的话尽量开两倍
跑对拍一定要跑几组极限数据，看看会不会RE什么的

发现q比较大，单次操作最慢也得是\(O(log^2n)\)的

都是区间加减，拆成n列直接差分的话单次操作是\(O(n)\)的，有点悬

注意到这里是等腰直角三角形，标记可以斜着传

那就在左上顶点打一个加法标记，左下顶点打一个减法标记

加法标记向正下和右下传，减法标记向右边传

然后标记直接互相抵消还有不少细节

Code:

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 1010

#define ll long long

#define ld long double

#define usd unsigned

#define ull unsigned long long

//#define int long long 

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)

char buf[1<<21], *p1=buf, *p2=buf;

inline int read() {

	int ans=0, f=1; char c=getchar();

	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}

	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}

	return ans*f;

}

int n, q;

namespace force{

	ll mat[N][N];

	void solve() {

		int r, c, l, s;

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

			r=read(); c=read(); l=read(); s=read();

			for (int x=r; x<r+l&&x<=n; ++x)

				for (int y=c; y<=x-r+c&&y<=n; ++y)

					mat[x][y]+=s;

		}

		ll ans=0;

		for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) ans^=mat[i][j];

		//for (int i=1; i<=n; ++i) {for (int j=1; j<=n; ++j) cout<<mat[i][j]<<' '; cout<<endl;}

		printf("%lld\n", ans);

	}

}

namespace task2{

	ll mat[N][N], tag1[N][N], tag2[N][N];

	void solve() {

		int r, c, l, s;

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

			r=read(); c=read(); l=read(); s=read();

			tag1[r][c]+=s; tag1[min(r+l+1, n+1)][min(c+l+1, n+1)]-=s;

			tag2[min(r+l, n+1)][c]-=s; tag2[min(r+l, n+1)][min(c+l+1, n+1)]+=s;

		}

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

			ll now=0;

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

				now+=tag1[i][j]+tag2[i][j];// now+=tag2[i][j];

				mat[i][j]=now;

				//tag1[i][j]+=tag2[i][j];

				//assert(tag1[i][j]==now);

				tag1[i+1][j+1]+=tag1[i][j];

				tag2[i][j+1]+=tag2[i][j];

				//tag2[i][j+1]+=tag2[i][j];

			}

		}

		ll ans=0;

		for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) ans^=mat[i][j];

		//for (int i=1; i<=n; ++i) {for (int j=1; j<=n; ++j) cout<<mat[i][j]<<' '; cout<<endl;}

		printf("%lld\n", ans);

	}

}

signed main()

{

	#ifdef DEBUG

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

	#endif

	n=read(); q=read();

	if (!q) {puts("0"); return 0;}

	//force::solve();

	task2::solve();

	return 0;

}

巴特西

题解 u

最新文章

热门文章