今天是满课的一天，于是我找了个水题，单纯的求逆序对！题目求逆序对 本题的标答似乎是在归并排序的过程中记录交换的次数，不过我灵机一动就拿离散化加上求逆序对的操作求证了一遍，发现也非常能用，而且也是O(nlogn）的复杂度，完全能冲。
代码如下
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> P; const int maxn = 5e5 + 5; ll c[maxn << 2], n; void add(ll t) { while (t <= n) { c[t]++; t += t & (-t); } } ll sum(ll t) { ll res = 0; while (t >= 1) { res += c[t]; t -= t & (-t); } return res; } P p[maxn]; ll nxt[maxn]; void M_sort() { sort(p + 1, p + 1 + n); for (int i = 1; i <= n; i++) { nxt[p[i].second] = i; } } int main() { scanf("%d", &n); for (int i = 1; i <= n;i++) { ll x; scanf("%lld", &x); p[i] = P(x, i); } M_sort(); ll ans = 0; for (int i = n; i >= 1;i--) { //printf("%d ", nxt[i]); int v = n - nxt[i] + 1; add(v); ans += i-sum(v); } printf("%lld", ans); }