E - Ball Coloring AtCoder Regular Contest 073

問題概略
2個の白いボールが入った袋がN個あり、それらには数字が書いてある。
袋のボールを赤と青に塗り分けた時、(rmax - rmin) * (bmax - bmin) を最小化したい

制約
N<=2 * 10^5
x,y <= 10^9

解法
全体の最大値、最小値は必ずどちらかに含まれる。
よって赤大 赤小　赤大 青小の2パターンがある。
後者は赤になるべく大きいものを入れ、青に小さいものを入れれば良い。
前者について考える。
わかりやすくするためx,yを左のほうが小さく、昇順になるようにする。
xをbに入れ事を考えると、現在最大値はこれより小さく出来ず、差を減らすには最小値を交換するしか無いことがわかる。
つまり、昇順にした後に上からいくつかを交換すれば良い。o(N)

Submission #3181054 - AtCoder Regular Contest 073

 public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        int[] x = niah(N, 2);
        int[] y = niah(N, 2);
        {
            int[] r = new int[N];
            int[] b = new int[N];
            for (int i = 0; i < N; i++) {
                r[i] = max(x[i], y[i]);
                b[i] = min(x[i], y[i]);
            }
            chMin(((long) max(r) - min(r)) * ((long) max(b) - min(b)));
        }
        {
            P[] p = new P[N];
            for (int i = 0; i < N; i++) {
                p[i] = new P(min(x[i], y[i]), max(x[i], y[i]));
            }
            sort(p);
            long maxr = max(max(x), max(y));
            long minr = min(min(x), min(y));
            SegmentTree seg = new SegmentTree(N);
            for (int i = 0; i < N; i++) {
                seg.update(i, p[i].x);
            }
            //i個入れ替える
            for (int i = 0; i < N + 1; i++) {
                if (i != 0) seg.update(i - 1, p[i - 1].y);
                chMin((maxr - minr) * ((long) seg.max(0, N) - seg.min(0, N)));
            }
        }
        System.out.println(minRes);
    }