CodeIQ の問題 「交差点をすばやく数えよう！」 https://codeiq.jp/ace/yuki_hiroshi/q432 の回答。

CrossingSolver.java

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;

/**
 * CodeIQ の問題 [交差点をすばやく数えよう！](https://codeiq.jp/ace/yuki_hiroshi/q432) の回答です。
 *
 * @author KOMIYA Atsushi
 */
public class CrossingSolver {
    /**
     * エントリポイント。
     *
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {

        long begin = System.currentTimeMillis();

        int[] values = load("crossing.txt");

        long loadEnd = System.currentTimeMillis();

        long crossingCount = calculateCrossing(values);

        long end = System.currentTimeMillis();

        System.out.println("交差点の数 : " + crossingCount);
        System.out.println("処理時間[ms] : " + (end - begin));

        System.out.println("ロード時間 : " + (loadEnd - begin));
        System.out.println("計算時間 : " + (end - loadEnd));
    }

    /**
     * 指定されたファイル名のテキストファイルに記述されている「クロッシング問題」を読み込み、
     * int の配列に変換して返却します。
     *
     * @param filename 問題が記述されているファイルの名前
     * @return ファイルを読み込んだ結果を保持した int の配列
     * @throws IOException
     */
    static int[] load(String filename) throws IOException {
        int[] work = new int[1024];
        int lineCount = 0;

        try (FileReader fr = new FileReader(filename);
             BufferedReader reader = new BufferedReader(fr)) {

            String line;
            while ((line = reader.readLine()) != null) {
                if (lineCount >= work.length) {
                    work = Arrays.copyOf(work, work.length * 2);
                }
                work[lineCount++] = parseInt(line);
            }
        }

        return Arrays.copyOf(work, lineCount);
    }

    /**
     * 文字列表現された 10 進数を数値を int 値に変換します。
     *
     * @param val
     * @return
     */
    static int parseInt(String val) {
        int result = 0;
        for (int i = 0, len = val.length(); i < len; i++) {
            result = result * 10 + val.charAt(i) - '0';
        }
        return result;
    }

    /**
     * 引数で指定された「クロッシング問題」を解き、交差点の数を返却します。
     *
     * @param values クロッシング問題を表す int 値の配列です
     * @return 交差点の数
     */
    static long calculateCrossing(int[] values) {
        BitVector bitVector = new BitVector(values.length);

        long result = 0;
        for (int i = 0; i < values.length; i++) {
            final int destIndex = i;
            final int srcIndex = values[i] - 1;
            final int usedCount = bitVector.bitCount1(srcIndex);
            final int crossingCount = (srcIndex - usedCount) + (destIndex - usedCount);

            result += crossingCount;

            bitVector.set1(srcIndex);
        }

        return result / 2;
    }

    /**
     * ビット値を保持するベクトルです。
     * <p>
     * rank 操作に相当する {@link #bitCount1(int)} を効率的に行うための
     * 動的更新される辞書を内部で保持しています。
     * </p>
     *
     * @author KOMIYA Atsushi
     */
    public static class BitVector {
        private static final int RELATIVE_BIT_SIZE = 512;
        private static final int ABSOLUTE_BIT_SIZE = 4096;
        private final long[] bits;
        private final int[] relativeBitCounts;
        private final int[] absoluteBitCounts;

        /**
         * 指定された個数のビット値を保持する BitVector オブジェクトを生成します。
         *
         * @param size 保持するビット値の個数
         */
        BitVector(int size) {
            final int numBufferBits = size + ABSOLUTE_BIT_SIZE - 1;

            this.bits = new long[numBufferBits / 64];

            this.relativeBitCounts = new int[numBufferBits / RELATIVE_BIT_SIZE];
            this.absoluteBitCounts = new int[numBufferBits / ABSOLUTE_BIT_SIZE];
        }

        /**
         * 指定されたビットインデックスの位置の要素をビット 1 とします。
         *
         * @param bitIndex ビット 1 を設定したい位置を示すビットインデックス
         */
        public void set1(int bitIndex) {
            final int bitsArrayIndex = bitIndex / 64;
            final int bitsInBitIndex = bitIndex % 64;

            bits[bitsArrayIndex] |= 1L << bitsInBitIndex;

            final int relativeArrayIndex = bitIndex / RELATIVE_BIT_SIZE;
            relativeBitCounts[relativeArrayIndex]++;

            final int absoluteArrayIndex = bitIndex / ABSOLUTE_BIT_SIZE;
            for (int i = absoluteArrayIndex + 1; i < absoluteBitCounts.length; i++) {
                absoluteBitCounts[i]++;
            }
        }

        /**
         * 指定されたビットインデックスを含む、左側の区間 [0, bitIndex] において、ビット 1 の個数を算出します。
         *
         * @param bitIndex ビット 1 の個数を算出したい、0 から始まる区間の右端を表すビットインデックス
         * @return [0, bitIndex] の間のビット 1 の個数
         */
        public int bitCount1(int bitIndex) {
            final int absoluteArrayIndex = bitIndex / ABSOLUTE_BIT_SIZE;
            int result = absoluteBitCounts[absoluteArrayIndex];

            final int beginRelativeArrayIndex = absoluteArrayIndex * ABSOLUTE_BIT_SIZE / RELATIVE_BIT_SIZE;
            final int targetRelativeArrayIndex = bitIndex / RELATIVE_BIT_SIZE;

            for (int i = beginRelativeArrayIndex; i < targetRelativeArrayIndex; i++) {
                result += relativeBitCounts[i];
            }

            final int beginBitsArrayIndex = targetRelativeArrayIndex * RELATIVE_BIT_SIZE / 64;
            final int targetBitsArrayIndex = bitIndex / 64;

            for (int i = beginBitsArrayIndex; i < targetBitsArrayIndex; i++) {
                result += Long.bitCount(bits[i]);
            }

            final int bitsInBitIndex = bitIndex % 64;
            final long mask = (1L << bitsInBitIndex) - 1;

            result += Long.bitCount(bits[targetBitsArrayIndex] & mask);

            return result;
        }
    }
}