E - Sorted and Sorted AtCoder Regular Contest 097

問題概略
1 ~ Nが書かれた、白と黒のボールが2N個並べられている。
隣り合う２つのボールを入れ替えることが出来る時、白黒をそれぞれの色についてソートするのにかかる最小手数はなにか。

制約
1 <= N <= 2000

解法
実際にソートする時の事を考えると、左詰めにやっていきたい。
また、ある左までがソート完了している時、白は1~i,黒は1~jのように並んでいて、右に残っているものは一定である。
つまりi,jの値で状態をまとめられる。
i,jまでソートしている時、次に左に持ってこれるのはi+1かj+1であり、全ての数の位置と、その左にある数以上の玉がいくつあるかを数えられれば持ってくる時のスワップ回数がわかる。これは二次元累積和（位置、数）を使えばO(1)

問題の芯
最終手に作りたい形がある場合、とりあえず左詰めで考える。
また状態がまとめられるということに気づく

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        char[] c = new char[2 * N];
        int[] a = new int[2 * N];
        int[][] pb = new int[2 * N][N];
        int[][] pw = new int[2 * N][N];
        int[] posb = new int[N];
        int[] posw = new int[N];
        for (int i = 0; i < 2 * N; i++) {
            c[i] = nc();
            a[i] = ni() - 1;
            if (c[i] == 'B') {
                pb[i][a[i]]++;
                posb[a[i]] = i;
            } else {
                pw[i][a[i]]++;
                posw[a[i]] = i;
            }
        }

        RectangleSum recb = new RectangleSum(pb);
        RectangleSum recw = new RectangleSum(pw);
        int[][] dp = new int[N + 1][N + 1];
        fill(dp, INF);
        dp[0][0] = 0;
        //ij個を左詰めにする最小
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < N + 1; j++) {
                if (i == N && j == N) continue;
                if (i < N) {
                    //pより左の i+1> j>
                    //2個ある時、次に来るのは2
                    int coub = (int) recb.getSum(i + 1, N, 0, posb[i]);
                    int couw = (int) recw.getSum(j, N, 0, posb[i]);
                    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + coub + couw);
                }
                if (j < N) {
                    int coub = (int) recb.getSum(i, N, 0, posw[j]);
                    int couw = (int) recw.getSum(j + 1, N, 0, posw[j]);
                    dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + coub+couw);
                }
            }
        }
        System.out.println(dp[N][N]);
    }

    //値を渡す際は半開区間
    static class RectangleSum {
        //半開区間 0は0
        long[][] rui;
        int H, W;

        RectangleSum(long[][] ori) {
            H = ori.length;
            W = ori[0].length;
            rui = new long[H + 1][W + 1];
            for (int hi = 0; hi < H; hi++) {
                for (int wi = 0; wi < W; wi++) {
                    rui[hi + 1][wi + 1] = ori[hi][wi];
                }
            }
            for (int hi = 1; hi < H + 1; hi++) {
                for (int wi = 1; wi < W + 1; wi++) {
                    rui[hi][wi] += rui[hi - 1][wi];
                    rui[hi][wi] += rui[hi][wi - 1];
                    rui[hi][wi] -= rui[hi - 1][wi - 1];
                }
            }
        }

        RectangleSum(int[][] ori) {
            H = ori.length;
            W = ori[0].length;
            rui = new long[H + 1][W + 1];
            for (int hi = 0; hi < H; hi++) {
                for (int wi = 0; wi < W; wi++) {
                    rui[hi + 1][wi + 1] = ori[hi][wi];
                }
            }
            for (int hi = 1; hi < H + 1; hi++) {
                for (int wi = 1; wi < W + 1; wi++) {
                    rui[hi][wi] += rui[hi - 1][wi];
                    rui[hi][wi] += rui[hi][wi - 1];
                    rui[hi][wi] -= rui[hi - 1][wi - 1];
                }
            }
        }

        //半開区間
        public long getSum(int left, int right, int top, int bottom) {
            if (right > W || bottom > H) return 0;
            if (left < 0 || top < 0) return 0;
            if (top >= bottom || left >= right) return 0;
            long res = rui[bottom][right];
            res -= rui[top][right];
            res -= rui[bottom][left];
            res += rui[top][left];
            return res;
        }

    }