• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# Untitled

a guest Sep 30th, 2012 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.           }
RAW Paste Data
Top