Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 30th, 2012  |  syntax: C  |  size: 0.96 KB  |  views: 25  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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.           }
clone this paste RAW Paste Data