Codeforces Round #301 Div2 E: Infinite Inversions (Binary Indexed Tree)

問題

解法

下記リンクで丁寧に解説されている。
Codeforces Round #301 (Div. 2) E. Infinite Inversions - mayoko’s diary
Codeforces #301 Div2 E. Infinite Inversions - kmjp's blog

Binary Indexed Tree については以下の問題を通して理解できる。
反転数 | アルゴリズムとデータ構造 | Aizu Online Judge

反点数の組み合わせについて、2つともswapされた数だった場合、上記のAOJの問題と全く同じ方法で求めることが出来る。

コード

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		HashMap<Integer, Integer> hashMap = new HashMap<>();
		for (int i = 0; i < n; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			if (hashMap.get(x) == null) {
				hashMap.put(x, x);
			}
			if (hashMap.get(y) == null) {
				hashMap.put(y, y);
			}

			int tmp = hashMap.get(x);
			hashMap.put(x, hashMap.get(y));
			hashMap.put(y, tmp);
		}
		sc.close();

		ArrayList<Integer> keyList = new ArrayList<>();
		for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
			keyList.add(entry.getKey());
		}
		Collections.sort(keyList);

		HashMap<Integer, Integer> keyMap = new HashMap<>();
		for (int i = 0; i < keyList.size(); i++) {
			keyMap.put(keyList.get(i), i + 1);
		}

		BinaryIndexedTree tree = new BinaryIndexedTree(hashMap.size());
		long ans = 0;
		for (Integer index : keyList) {
			int num = hashMap.get(index);

			ans += Math.abs(index - num) - Math.abs(keyMap.get(index) - keyMap.get(num));
			ans += tree.sum(hashMap.size()) - tree.sum(keyMap.get(num));
			tree.add(keyMap.get(num), 1);
		}
		System.out.println(ans);

	}

	static class BinaryIndexedTree {
		int N;
		long[] bit;

		public BinaryIndexedTree(int N) {
			this.N = N;
			bit = new long[N + 1];

		}

		public int sum(int i) {
			int sum = 0;
			while (i > 0) {
				sum += bit[i];
				i -= i & -i;
			}
			return sum;
		}

		public void add(int i, int x) {
			while (i <= N) {
				bit[i] += x;
				i += i & -i;
			}
		}
	}

}