//求逆序对,归并排序就好 #include <iostream> using namespace std; typedef long long ll; int n; ll cnt = 0; int a[100005], b[100005]; void print() { int i; for (i = 1; i <= n; i++) cout << a[i] << " "; cout << endl; } void _merge(int l, int mid, int r) { int i; int p1 = l, p2 = mid + 1; for (i = l; i <= r; i++) if ((p1 <= mid) && ((p2 > r) || (a[p1] <= a[p2]))) { b[i] = a[p1]; p1++; } else { cnt += mid - p1 + 1; b[i] = a[p2]; p2++; } for (i = l; i <= r; i++) a[i] = b[i]; } void erfen(int l, int r) { int mid = (l + r) >> 1; if (l < r) { erfen(l, mid); erfen(mid + 1, r); } _merge(l, mid, r); } int main() { int i; cin >> n; for (i = 1; i <= n; i++) cin >> a[i]; erfen(1, n); cout << cnt << endl; } —————————————————————————————————————— #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <cstdlib> #include <algorithm> #include <map> #include <vector> #include <queue> #include <set> using namespace std; #define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++) #define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--) #define mst(v,s) memset(v,s,sizeof(v)) #define pb push_back #define IOS ios::sync_with_stdio(false) #define int long long #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define ls p<<1 #define rs p<<1|1 #define lson p<<1,l,mid #define rson p<<1|1,mid+1,r #define sf scanf typedef long long ll; typedef unsigned long long ull; const int N = 1e5 + 10; int a[N],b[N]; int n, q; int tr[4 * N]; void pushup(int p) { tr[p] = tr[ls] + tr[rs]; } void update(int p, int l, int r, int x) { if (l == r) { tr[p]++; return; } int mid = (l + r) >> 1; if (x <= mid) update(lson, x); else update(rson, x); pushup(p); } int find(int p, int l, int r, int x, int y) { if (x <= l && r <= y) { return tr[p]; } int mid = (l + r) >> 1; if (y <= mid) return find(lson, x, y); else if(x >= mid + 1) return find(rson, x, y); return find(lson, x, mid) + find(rson, mid + 1, y); } //不用先建树 //从后往前(或者从前往后处理即可) //把后一个数x加进线段树里,询问树上有多少数小于x,每次加上询问得到的值即可 signed main(void ) { //!!! //freopen("data.txt", "r", stdin); //!!! IOS; cin >> n; _for(i, 1, n) cin >> a[i],b[i]=a[i]; sort(b + 1, b + 1 + n); //不用去重离散也行,数据范围小,主要是练习一下离散 int tot = unique(b + 1, b + 1 + n) - b -1; ll ans = 0; _rep(i,n,1) { int p = lower_bound(b + 1, b + 1 + n, a[i]) - b; update(1, 1, n, p); if (i == n || a[i] == 1 ) continue;//最后一个数和a[i]为1时直接跳过 ans += find(1, 1, tot, 1, p - 1); } cout << ans << endl; }