Triangular Updates [CSAcademy #68 D]

https://csacademy.com/contest/round-68/task/triangular-updates/

N*Nの行列があり、最初は全て0.
以下のクエリをQ個処理した後の行列を答えよ。
「(R,L)を左上として縦L,横Lの直角三角形の領域にSを足す」
（例を見ると分かりやすい）

前提知識

• imos法

解法

imos法を使っていく。
例えば「右上が(1,1)で縦横3で4だけ出す」というクエリについて考える。
横に更新していくimos法を考えると、

4 -4 0 0 0
4 0 -4 0 0
4 0 0 -4 0
0 0 0 0 0

のように更新したい。これを横にimos法で更新すると

4 0 0 0 0
4 4 0 0 0
4 4 4 0 0
0 0 0 0 0

となる。
上のように加算するために

• 行列A : 縦方向のimos法
• 行列B : 対角線方向のimos法

の2つを用意して更新しよう。
　
まず4を実現するためにAに以下のように足す

4 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-4 0 0 0 0

これで全てのクエリの後に縦にimos法を使えばOK
　
次に-4を実現するためにBに以下のように足す

0 -4 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 4

これで全てのクエリの後に対角線にimos法を使えばOK
　
最終的に作りたかったのは、A+Bの行列なので、それぞれimos法をしたらAにBを足して、最後に横方向にimos法をやれば、全体を高速に得られる。

int N, Q;
ll A[2010][2010], B[2010][2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(q, 0, Q) {
        int y, x, l, s;
        cin >> y >> x >> l >> s;
        y--; x--;

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

        B[y][x + 1] -= s;
        B[y + l][x + l + 1] += s;
    }

    rep(x, 0, N) rep(y, 1, N) A[y][x] += A[y - 1][x];
    rep(x, 0, N) rep(y, 0, N) if (x and y) B[y][x] += B[y - 1][x - 1];
    rep(x, 0, N) rep(y, 0, N) A[y][x] += B[y][x];
    rep(y, 0, N) rep(x, 1, N) A[y][x] += A[y][x - 1];

    rep(y, 0, N) {
        rep(x, 0, N) {
            if (x) printf(" ");
            printf("%lld", A[y][x]);
        }
        printf("\n");
    }
}