题目传送门
树状数组+求逆序对
#include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; #define lowbit(x) (x & -x) const int N = 500010; // a是原始数组 struct Node { int w, id; } a[N]; bool cmp(Node a, Node b) { //本题题目保证，数据没有重复的 return a.w < b.w; } // d是原始数组离散化后的数组 / t是树状数组 int d[N], t[N]; LL getsum(int x) { LL sum = 0; while (x) sum += t[x], x -= lowbit(x); return sum; } void add(int x, int d) { while (x <= N) t[x] += d, x += lowbit(x); } int main() { int n; //题目解析： 用树状数组做，向下更新，向上求和，因为数据范围太大，但是每个数都不一样所以先离散化一下； //此题目也可以使用离散化，但性能差了5倍左右，也能AC while (~scanf("%d", &n) && n) { //清空树状数组 memset(t, 0, sizeof(t)); //读入原始数组 for (int i = 1; i <= n; i++) { scanf("%d", &a[i].w); a[i].id = i; } //按w由小到大排序 sort(a + 1, a + 1 + n, cmp); //生成离散化后的数组 for (int i = 1; i <= n; i++) d[a[i].id] = i; //利用树状数组动态维护个数，动态获取前缀和（权值） LL ans = 0; for (int i = 1; i <= n; i++) { add(d[i], 1); //先加后查，把自己算里了 ans += i - getsum(d[i]); } printf("%lld\n", ans); } return 0; }