• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

题解 u

开发技术 开发技术 7小时前 4次浏览

传送门

  • 这里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("%lldn", 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("%lldn", 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
喜欢 (0)