#1151696 (Java) No.3469 ジャッジ結果の逆転数

• 問題: No.3469 ジャッジ結果の逆転数
• ユーザー: ks2m
• 提出日時: 2026-03-06 22:27:48
• 言語: Java (openjdk 25.0.2)
• 結果: AC
• 実行時間: 1,483 ms / 2,000 ms
• コード長: 1,650 bytes
• コンパイル時間: 2,783 ms
• コンパイル使用メモリ: 88,108 KB
• 実行使用メモリ: 80,752 KB
• 最終ジャッジ日時: 2026-03-06 22:28:07
• 合計ジャッジ時間: 16,977 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 17

ソースコード

import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		sc.close();

		int[] b = zaatu(a);
		long ans = tentousuu(b);
		System.out.println(ans);
	}

	static int[] zaatu(long[] a) {
		TreeMap<Long, Integer> map = new TreeMap<>();
		for (int i = 0; i < a.length; i++) {
			map.put(a[i], null);
		}
		Long[] arr = map.keySet().toArray(new Long[0]);
		int cnt = 0;
		for (Long i : arr) {
			cnt++;
			map.put(i, cnt);
		}
		int[] b = new int[a.length];
		for (int i = 0; i < a.length; i++) {
			b[i] = map.get(a[i]);
		}
		return b;
	}

	static long tentousuu(int[] a) {
		int n = a.length;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			min = Math.min(min, a[i]);
			max = Math.max(max, a[i]);
		}
		min--;
		int[] b = new int[n];
		for (int i = 0; i < n; i++) {
			b[i] = a[i] - min;
		}

		BIT bit = new BIT(max - min);
		long ret = 0;
		for (int i = 0; i < n; i++) {
			ret += i - bit.sum(b[i]);
			bit.add(b[i], 1);
		}
		return ret;
	}

	/**
	 * Binary Indexed Tree
	 * 要素数nで初期化
	 * add、sumは1-indexed
	 */
	static class BIT {
		int n;
		long[] arr;

		public BIT(int n) {
			this.n = n;
			arr = new long[n + 1];
		}

		void add(int idx, long val) {
			for (int i = idx; i <= n; i += i & -i) {
				arr[i] += val;
			}
		}

		long sum(int idx) {
			long sum = 0;
			for (int i = idx; i > 0; i -= i & -i) {
				sum += arr[i];
			}
			return sum;
		}
	}
}