ABC106-D：AtCoder Express 2

累積和 二次元累積和

問題

https://beta.atcoder.jp/contests/abc106/tasks/abc106_d

M つの区間 [l_i, r_i] が与えられる。またクエリが Q つ与えられる。以下のクエリの数を求めよ。

クエリ
2つの数 [p_i, q_i] に完全に含まれる (p_i <= l_j かつ r_j <= q_i) 区間の個数を求めよ。

制約

  • 1 <= N <= 500
  • 1 <= M <= 2 * 105
  • 1 <= Q <= 105

考え方

解法1(区間を座標と対応させる)

与えられる各区間 [l_i, r_i] を2次元上の点 (l_i, r_i) としてプロットすると以下のようになる。

例）サンプル3でクエリ [2, 8] に含まれる区間の個数を求める場合

f:id:d_tutuz:20180819062839p:plain

求める区間の個数は、クエリ [p_i, q_i] に完全に含まれる区間の個数であるから、上の2次元上の (p_i, p_i) から (q_i, q_i) を頂点とする長方形の中に含まれる頂点の個数に対応する。上の例では (2, 2) から (8, 8) を頂点とする長方形に含まれる領域を緑背景としている。この領域の中に含まれる頂点数は 6 であり、これが各クエリで出力すべき解である。

各クエリに対してはO(1)で対応したい。これは与えられた区間を元に二次元累積和を構築すればよい。計算量は、構築に O(N2 + M) で各クエリでO(Q)であるから、全体として O(N2 + M + Q) である。なお、二次元累積和は予めライブラリとして持っておくと便利である。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int N = in.nextInt();
            int M = in.nextInt();
            int Q = in.nextInt();

            int[][] mat = new int[N+1][N+1];
            int[][] sum = new int[N+1][N+1];

            for (int i = 0; i < M; i++) {
                int l = in.nextInt();
                int r = in.nextInt();
                mat[l][r]++;
            }

            for (int i = 0; i < N+1; i++) {
                for (int j = 0; j < N+1; j++) {
                    sum[i][j] = mat[i][j];
                    if (j-1 >= 0) sum[i][j] += sum[i][j-1];
                    if (i-1 >= 0) sum[i][j] += sum[i-1][j];
                    if (i-1 >= 0 && j-1 >= 0) sum[i][j] -= sum[i-1][j-1];
                }
            }

            for (int i = 0; i < Q; i++) {
                int p = in.nextInt();
                int q = in.nextInt();

                int count = get(p, p, q, q, sum);
                out.println(count);
            }

        }

        int get(int x1, int y1, int x2, int y2, int[][] sum) {

            int res = sum[x2][y2];
            if (x1 > 0) res -= sum[x1-1][y2];
            if (y1 > 0) res -= sum[x2][y1-1];
            if (x1 > 0 && y1 > 0) res += sum[x1-1][y1-1];

            return res;
        }

解法2(ソート)

確認中

ポイント

  • 各区間の情報を二次元上の座標に対応させる

類題

雑記

本番中は最初、区間 [l_i, r_i] を左端、右端別々に分けて個数を数えようとした。求める区間は右端と左端が連続になっている必要があり、独立に考えてはいけない。以下のブログを参考に二次元にマッピングして数える方法で求められることがわかったので、実装してACした。