C语言 | Leetcode C语言题解之第493题翻转对

题目：

题解：

int lowbit(int x) {return x & (-x);
}void update(int* tree, int treeSize, int x, int d) {while (x <= treeSize) {tree[x] += d;x += lowbit(x);}
}int query(int* tree, int x) {int ans = 0;while (x) {ans += tree[x];x -= lowbit(x);}return ans;
}int cmp(void* _a, void* _b) {long long a = *((long long*)_a), b = *((long long*)_b);return a < b ? -1 : 1;
}int lower_bound(long long* a, int aSize, long long target) {int left = 0, right = aSize;while (left < right) {int mid = (left + right) / 2;if (a[mid] < target) {left = mid + 1;} else {right = mid;}}return left;
}int discrete(int* nums, int numsSize, int* ret) {long long rec[numsSize * 2];for (int i = 0; i < numsSize; i++) {rec[i * 2] = nums[i], rec[i * 2 + 1] = (long long)nums[i] * 2;}qsort(rec, numsSize * 2, sizeof(long long), cmp);int retSize = 0;for (int i = 0; i < numsSize * 2; i++) {if (retSize == 0 || rec[retSize - 1] != rec[i]) {rec[retSize++] = rec[i];}}for (int i = 0; i < numsSize; i++) {ret[i * 2] = lower_bound(rec, retSize, nums[i]) + 1;ret[i * 2 + 1] = lower_bound(rec, retSize, (long long)nums[i] * 2) + 1;}return retSize;
}int reversePairs(int* nums, int numsSize) {if (numsSize == 0) {return 0;}int values[numsSize * 2];int valuesSize = discrete(nums, numsSize, values);int ret = 0;int tree[valuesSize + 2];memset(tree, 0, sizeof(tree));for (int i = 0; i < numsSize; i++) {int left = values[i * 2 + 1], right = valuesSize + 1;ret += query(tree, right) - query(tree, left);update(tree, valuesSize + 1, values[i * 2], 1);}return ret;
}