题目就是让你求逆序数，用树状数组很简单，不过数据太大，，要先进行离散化，将数据范围压缩到1~n以内。还有poj竟然不支持c++11，害得我lambda表达式编译错误。
#include <iostream>#include <sstream>#include <fstream>#include <string>#include <map>#include <vector>#include <list>#include <set>#include <stack>#include <queue>#include <deque>#include <algorithm>#include <functional>#include <iomanip>#include <limits>#include <new>#include <utility>#include <iterator>#include <cstdio>#include <cstdlib>#include <cstring>#include <cctype>#include <cmath>#include <ctime>using namespace std;const int maxn = 500010;int bit[maxn], n;struct ST{int num, index;};ST a[maxn];//树状数组求和int sum(int i){int s = 0;while (i > 0){s += bit[i];i &= i – 1;}return s;}//树状数组修改元素void add(int i, int x){while (i <= n){bit[i] += x;i += i & (-i);}}int main(){while (scanf("%d", &n) == 1 && n){memset(bit, 0, sizeof(bit));for (int i = 0; i < n; ++i){scanf("%d", &a[i].num);a[i].index = i;}//离散化sort(a, a+n, [](ST a, ST b){ return a.num < b.num; });int cnt = 0, tmp;for (int i = 0; i < n; ++i)if (!i || a[i].num != tmp){tmp = a[i].num;a[i].num = ++cnt;}else{tmp = a[i].num;a[i].num = cnt;}sort(a, a+n, [](ST a, ST b){ return a.index < b.index; });//树状数组求逆序数long long ans = 0;for (int i = 0; i < n; ++i){ans += i – sum(a[i].num);add(a[i].num, 1);}cout << ans << endl;}return 0;}
版权声明：本文为博主原创文章，转载请注明出处。
在乎的应该是沿途的风景以及看风景的心情。
