POJ 1990 MooFest

http://poj.org/problem?id=1990

Every year, Farmer John's N (1 <= N <= 20,000) cows attend "MooFest",a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a bit of their hearing.

Each cow i has an associated "hearing" threshold v(i) (in the range 1..20,000). If a cow moos to cow i, she must use a volume of at least v(i) times the distance between the two cows in order to be heard by cow i. If two cows i and j wish to converse, they must speak at a volume level equal to the distance between them times max(v(i),v(j)).

Suppose each of the N cows is standing in a straight line (each cow at some unique x coordinate in the range 1..20,000), and every pair of cows is carrying on a conversation using the smallest possible volume.

Compute the sum of all the volumes produced by all N(N-1)/2 pairs of mooing cows. 

Input

* Line 1: A single integer, N

* Lines 2..N+1: Two integers: the volume threshold and x coordinate for a cow. Line 2 represents the first cow; line 3 represents the second cow; and so on. No two cows will stand at the same location. 

Output

* Line 1: A single line with a single integer that is the sum of all the volumes of the conversing cows. 

Sample Input

4
3 1
2 5
2 6
4 3

Sample Output

57
https://shanzi.gitbooks.io/algorithm-notes/content/problem_solutions/moo_fest.html

A simple problem need using binary indexed tree. At first we sort the cows according to their volumes, then we iterate over all cows and calculate the volume produced by current cow and added them into a binary indexed tree according to their position. As the cows is sorted by volumes so for each cow i, previous cows added in the tree all have volumes less than or equal to its volume. So the volume of converse should between i with these cows is i's volume. We can use binary indexed tree to fast query the number of cows on the left or right of i and apply different formular to calculate the total distance according to their distances to the left most coordinate.

As the position space is large and we can not cost so much memory, we have to find all distinct xcoordinate and compress them.

    private static void add(long[] bit, int i, int x) {
        while (i > 0 && i < bit.length) {
            bit[i] += x;
            i += i & -i;
        }
    }

    private static long query(long[] bit, int i) {
        long res = 0;
        while (i > 0 && i < bit.length) {
            res += bit[i];
            i -= i & -i;
        }
        return res;
    }

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

        while (in.hasNextInt()) {
            int N = in.nextInt();
            int[][] cows = new int[N][2];
            for (int i = 0; i < N; i++) {
                cows[i][0] = in.nextInt();
                cows[i][1] = in.nextInt();
            }

            Arrays.sort(cows, new Comparator<int[]> () {
                public int compare(int[] a, int[] b) {
                    return a[0] - b[0];
                }
            });

            long[] bitcount = new long[20001];
            long[] bitdistance = new long[20001];

            long res = 0;
            for (int i = 0; i < N; i++) {
                int vol = cows[i][0];
                int x = cows[i][1];
                long leftCount = query(bitcount, x);
                long rightCount = i - leftCount;
                long leftDistance = query(bitdistance, x);
                long rightDistance = query(bitdistance, 20000) - leftDistance;
                res += (leftCount * x - leftDistance + rightDistance - rightCount * x) * vol;
                add(bitcount, x, 1);
                add(bitdistance, x, x);
            }
            System.out.println(res);
        }
    }