C - Gr-idian MST CODE FESTIVAL 2016 qual B

C: Gr-idian MST - CODE FESTIVAL 2016 qual B | AtCoder
問題概略
(H+1)*(W+1)個の頂点がある。
隣り合う縦に辺を貼るのに必要なコストはxの大きさにかかわらずpi
横も同様にqiかかる。
最小で全域機を作れ

制約
H,W <= 10^5
p,q<=10^8

解法
線を引いて考えてみると、辺の本数は一定であると気づく(H*W)+H+W本
また、辺を何回か回転することですべての形が作れそうだなと感じる。
すべての頂点に対して、右か上か小さい方を選んで全域機を作れるのではないかという気分になる。
しかし、このままではつながらない場合がある。ここで縦、横のすべてのコストの辺はどこかしらで必要になることと、H*W+H+W本のH+Wのところがそれだと気づく。
上に横いっぱいに、右に縦いっぱいに辺を貼っておけば、さっきの方法で好きに辺を選んでも全域木になる
よってこの問題は、横の辺の中で縦よりコストが大きいものを入れ替えてやった合計を足していけば良いことになる。
これは累積をとってソートして二分探索すればいい。

類題
C - AND Grid

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        int W = ni();
        int H = ni();
        long[] w = nla(W);
        long[] h = nla(H);
        long res = sum(w) + sum(h);
        sort(w);
        sort(h);
        long[] ruiw = rui(w);
        long[] ruih = rui(h);
        long sumw = sum(w);
        long sumh = sum(h);
        for (int i = 0; i < H; i++) {
            int ind = lowerBound(w, h[i]);
            long sum = sumw - (ruiw[W] - ruiw[ind]);
            sum += h[i] * (W - ind);
            res += sum;
        }
        System.out.println(res);
    }