ModularQuadrant [SRM744 Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=15236

マス(r,c)にmax(r,c) mod 3が書かれた平面がある。
この平面の左下が(r1, c1)、右上が(r2, c2)である長方形の総和を答えよ。

解説

以下説明のため、r=x, c=yとして説明する。
　
問題を簡単化するために、関数fという小問題に分割する。
f(x,y) := 左下(0,0)右上(x,y)である長方形の総和
これを使うと、f(r2,c2) - f(r2, c1-1) - f(r1 - 1, c2) + f(r1 - 1, c1 - 1)が答えになる。
なので、関数fの構築を考えよう。
　
まず、f(x,y)=f(y,x)であるので、x≦yであると考える。
① (0,0)～(x,x)の正方形
② (0, x+1)～(x, y)の残りの長方形
これを分けて計算しよう。
　
①
1は原点に近い方から1の円を見ていくと、3, 9, 15, ...と個数が増えている。
2は原点に近い方から2の円を見ていくと、5, 11, 17, ...と個数が増えている。
1の円の個数a1は(x+2)/3で得られる。
2の円の個数a2は(x+1)/3で得られる。
1の3,9,15,...のa1個目までの総和は3*a1*(a1+1)-3*a1である。
2の5,11,17,...のa2個目までの総和は3*a2*(a2+1)-a2である。
よって、正方形の総和は、
3LL * a1 * (a1 + 1) - 3LL * a1 + (3LL * a2 * (a2 + 1) - 1LL * a2) * 2
となる。
　
②
長方形部分は012012のしましま模様状になるので、1と2のシマシマの本数を数えよう。
これは(0,0)～(y,y)の正方形における1の円の個数をb1(=(y+2)/3)、2の円の個数をb2(=(y+1)/3)とすると、
1の本数はb1-a1, 2の本数はb2-a2となる。
シマシマの横幅はx+1なので、長方形部分の総和は、
(b1 - a1) * (x + 1) + (b2 - a2) * (x + 1) *2
となる。

ll f(int x, int y) {
    if (x < 0 or y < 0) return 0;

    if (x > y) return f(y, x);

    // x <= y

    int a1 = (x + 2) / 3;
    int a2 = (x + 1) / 3;

    int b1 = (y + 2) / 3;
    int b2 = (y + 1) / 3;

    ll res = 0;
    res += 3LL * a1 * (a1 + 1) - 3LL * a1;
    res += (3LL * a2 * (a2 + 1) - 1LL * a2) * 2;

    res += 1LL * (b1 - a1) * (x + 1);
    res += 1LL * (b2 - a2) * (x + 1) *2;

    return res;
}

struct ModularQuadrant {
    long long sum(int r1, int r2, int c1, int c2) {
        return f(r2, c2) - f(r2, c1 - 1) - f(r1 - 1, c2) + f(r1 - 1, c1 - 1);
    }
};