CSAcademy Round #68 : D. Triangular Updates

苦戦はしたけどどうにか解けて良かった。
https://csacademy.com/contest/round-68/task/triangular-updates/

問題

初期状態で各要素が0であるN*Nの二次元配列がある。
以下のクエリを順次適用し、各要素の値を答えよ。

• R,C,L,Sの4値が与えられる。(R,C)-(R+L-1,C)-(R+L-1,C+L-1)の3点を結ぶ直角三角形内の要素にSを加算する

解法

1クエリで面の範囲の値を更新するので、2回累積和を使って行くことを考えよう。
以下の2種類の累積和を考える。

• ある点に1加算すると、その下と右下の45度の間にある点全てが1加算される
• ある点に1加算すると、その下と右の90度の間にある点全てが1加算される

前者について(R,C)に+S、(R+L,C+L)に-S、後者について(R+L,C)に-S、(R+L,C+L)に+Sを加算すると、累積和を取った結果が題意に一致するようにできる。

int N,Q;

ll A[2020][2020];
ll B[2020][2020];
int Y,X,S,L;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	while(Q--) {
		cin>>Y>>X>>L>>S;
		Y--,X--;
		A[Y][X]+=S;
		A[Y+L][X+L]-=S;
		B[Y+L][X]-=S;
		B[Y+L][X+L]+=S;
	}
	FOR(y,N) FOR(x,N) {
		if(y&&x) A[y][x]+=A[y-1][x-1];
	}
	FOR(y,N) FOR(x,N) {
		if(x) B[y][x]+=B[y][x-1];
	}
	FOR(y,N) FOR(x,N) {
		if(y) A[y][x]+=A[y-1][x];
		if(y) B[y][x]+=B[y-1][x];
	}
	
	FOR(y,N) {
		FOR(x,N) cout<<A[y][x]+B[y][x]<<" ";
		cout<<endl;
		
	}
	
}

まとめ

最初O(NQ)な1次元の手抜き累積和使ったがギリギリTLEした。