Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!
tweet

Untitled

By: a guest on Sep 30th, 2012  |  syntax: C  |  size: 0.96 KB  |  views: 48  |  expires: Never
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.
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
Top