下面就是求逆序对的代码： #include<bits/stdc++.h> #define ll long long using namespace std; /* 题目描述 输入 ? n 个 1 ～ 1 0 9 1～10 9 范围内的整数，请输出包含多少逆序对。

输入格式 第一行一个整数 ? n。 接下来一行 ? n 个整数，含义如题意所述。

输出格式 一行一个整数。

输入数据 1 5 3 2 7 6 8 输出数据 1 2 数据规模与约定 对于 60 % 60% 的数据， 1 ≤ ? ≤ 1 0 3 1≤n≤10 3

对于 100 % 100% 的数据， 1 ≤ ? ≤ 1 0 6 1≤n≤10 6

数据保证纯随机生成。 */ const ll N=1e6+1; ll n,i,ans=0,a[N],b[N]; inline void merge(ll s,ll mid,ll t) { if(a[mid]<=a[mid+1]) return; ll i=s,j=mid+1,k=s; while(i<=mid&&j<=t){ if(a[i]<=a[j]) b[k++]=a[i++]; else{ ans+=mid-i+1; b[k++]=a[j++]; } } while(i<=mid) b[k++]=a[i++]; while(j<=t) b[k++]=a[j++]; for(i=s;i<=t;++i) a[i]=b[i]; } inline void merge_sort(ll s,ll t) { if(s==t) return; ll mid=(s+t)>>1; merge_sort(s,mid); merge_sort(mid+1,t); merge(s,mid,t); } int main() { scanf("%lld",&n); for(i=1;i<=n;++i) scanf("%lld",a+i); merge_sort(1,n); printf("%lld",ans); return 0; }