C83 树状数组 P1908 逆序对
树状数组版本：

#include<bits/stdc++.h>//树状数组版本
using namespace std;
const int N=5e5+10;
int a[N],b[N],c[N],n;
void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
int getsum(int x)
{
    int res=0;
    for(;x>=1;x-=x&-x)res+=c[x];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
	int nn=unique(b+1,b+n+1)-b-1;
	long long ans=0;
    memset(c,0,sizeof(c)); 
    for(int i=n;i>=1;i--)//让后面的数先出现，每次统计已经出现的有多少个比自己小的数的个数
    {
    	a[i]=lower_bound(b+1,b+nn+1,a[i])-b;
        add(a[i],1),ans+=getsum(a[i]-1);
    }
    printf("%lld\n",ans);
    return 0;
}

A14 归并排序 逆序对
A14 归并排序与逆序对（内网）

归并排序版本：

#include<bits/stdc++.h> //归并排序版本
using namespace std;
typedef long long ll;
const int N=5e5+10;
int a[N],tmp[N];
ll ans;
void msort(int l,int r)
{
    if(l>=r)return ;
    int mid=(l+r)/2;
    msort(l,mid);msort(mid+1,r);
    int len=l;
    int i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]>a[j])  tmp[len++]=a[j++],ans+=mid-i+1;
        else           tmp[len++]=a[i++];
    }
    while(i<=mid)tmp[len++]=a[i++];
    while(j<=r)tmp[len++]=a[j++];
    memcpy(a+l,tmp+l,(r-l+1)*4);
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    ans=0;msort(1,n);printf("%lld\n",ans);
    return 0;
}

C83 树状数组 P1908 逆序对
树状数组版本：

#include<bits/stdc++.h>//树状数组版本
using namespace std;
const int N=5e5+10;
int a[N],b[N],c[N],n;
void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
int getsum(int x)
{
    int res=0;
    for(;x>=1;x-=x&-x)res+=c[x];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
	int nn=unique(b+1,b+n+1)-b-1;
	long long ans=0;
    memset(c,0,sizeof(c)); 
    for(int i=n;i>=1;i--)//让后面的数先出现，每次统计已经出现的有多少个比自己小的数的个数
    {
    	a[i]=lower_bound(b+1,b+nn+1,a[i])-b;
        add(a[i],1),ans+=getsum(a[i]-1);
    }
    printf("%lld\n",ans);
    return 0;
}

A14 归并排序 逆序对

A14 归并排序 逆序对（内网）

归并排序版本：

#include<bits/stdc++.h> //归并排序版本
using namespace std;
typedef long long ll;
const int N=5e5+10;
int a[N],tmp[N];
ll ans;
void msort(int l,int r)
{
    if(l>=r)return ;
    int mid=(l+r)/2;
    msort(l,mid);msort(mid+1,r);
    int len=l;
    int i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]>a[j])  tmp[len++]=a[j++],ans+=mid-i+1;
        else           tmp[len++]=a[i++];
    }
    while(i<=mid)tmp[len++]=a[i++];
    while(j<=r)tmp[len++]=a[j++];
    memcpy(a+l,tmp+l,(r-l+1)*4);
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    ans=0;msort(1,n);
    printf("%lld\n",ans);
    return 0;
}