3067:Japan

keyword

2部グラフ　累積和　C++

概要

2部グラフ(1000*1000以下)が与えられる。ノードを番号順に並べたとき、辺の交点がいくつできるか求める問題。
いもす先生に教えてもらった。2次元配列a[n][m](a[i][j] = exist (i,j) in E)とする。その後各辺に対して、

図の斜線部の和を加算していく。加算は前処理で2次元累積和を計算しておくことにより定数時間で求まる。最後に重複がある分2で割れば答えが求まる。

static int accum[1010][1010];
static int xs[1000010], ys[1000010];

int main(){
    int i, j, x, y, n, m, k;
    int rept;

    rept = readint();

    LOOP(rept){
        n = readint(), m = readint(), k = readint();
        REP(i,n+1)REP(j,m+1) accum[i][j] = 0;
        REP(i,k){
            ys[i] = readint();
            xs[i] = readint();
            accum[ys[i]][xs[i]]++;
        }

        REPONE(i,n)REPONE(j,m){
            accum[i][j] += accum[i-1][j] + accum[i][j-1] - accum[i-1][j-1];
        }

        ll ans = 0;
        REP(i,k){
            x = xs[i];
            y = ys[i];
            ans += accum[y-1][m] - accum[y-1][x]
                    + accum[n][x-1] - accum[y][x-1];
        }

        printf("Test case %d: %lld\n",loopCount, ans/2);
    }

    return 0;
}