SHARE
TWEET

Untitled

a guest Sep 30th, 2012 50 Never
  1. // f is a frequency array. In your case, since n <= 10^5, declare it as int f[100004];
  2.  
  3. // The 2 methods below are code for Fenwick Tree, super short
  4. int rsq(int b) { // range sum query
  5.     int s = 0;
  6.     while (b) s += f[b], b -= b & -b;
  7.     return s;
  8. }
  9.  
  10. void adj(int k, int v) { // adjust
  11.      // L should be the maximum value in the array, but the maximum value and the length of the input happens to be the same, so I'm being sloppy here.
  12.      while (k <= L) f[k] += v, k += k & -k;  
  13. }
  14.  
  15. // main
  16.           s = 0; // Number of inversions
  17.           for (i = 1; i <= L; i++) { // L is the number of elements in the array
  18.               ... // Assign the current element in the array to v
  19.               adj(v, 1); // Adjust + 1 at value v in the Fenwick Tree
  20.               s += i - rsq(v); // rsq(v) will be the number of numbers smaller than or equal to v.
  21.                                // i - rsq(v) will be number of numbers strictly larger than v
  22.           }
RAW Paste Data
Top