樹狀數組求逆序對（逆序數）

逆序數（也叫逆序對）

在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大于後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。

【1】無重複的數

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define MAX 500000
typedef long long ll;
ll c[MAX];
ll n;
struct record
{
    ll val, pos;//記錄數值 和 位置
}num[MAX];
bool cmp(record a,record b)
{
    return a.val > b.val;
}
ll lowbit(ll x)
{
    return x&(-x);
}
ll sum(ll x)//求和
{
    ll s = ;
    while(x > )
    {
        s += c[x];
        x -= lowbit(x);
    }
    return s;
}
void update(ll x)//更新
{
    while(x <= n)
    {
        c[x] += ;
        x += lowbit(x);
    }
}
int main()
{
    ll i, j;
    ll x,y;
    ll ans;//統計總數目
    while(~scanf("%lld%lld%lld", &n,&x,&y))
    {
        memset(c, , sizeof(c));//初始化
        for(i = ;i < n; i++)
        {
            scanf("%lld", &num[i].val);
            num[i].pos = i + ;
        }
        sort(num, num+n, cmp);
        ans = ;
        for(i = ;i < n; ++i)//每一次插入目前最大值
        {
            update(num[i].pos);
            ans += sum(num[i].pos-);//統計前面有多少個數
        }
        ll anss=ans*min(x,y);
        printf("%lld\n",anss);
    }


}
           

【2】有重複的數

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define MAX 500000
typedef long long ll;
ll c[MAX];
ll n;
struct record
{
    ll val, pos;//記錄數值 和 位置
}num[MAX];
bool cmp(record a, record b)
{
    if(a.val != b.val)
    return a.val > b.val;
    else
    return a.pos > b.pos;
}

ll lowbit(ll x)
{
    return x&(-x);
}
ll sum(ll x)//求和
{
    ll s = ;
    while(x > )
    {
        s += c[x];
        x -= lowbit(x);
    }
    return s;
}
void update(ll x)//更新
{
    while(x <= n)
    {
        c[x] += ;
        x += lowbit(x);
    }
}
int main()
{
    ll i, j;
    ll x,y;
    ll ans;//統計總數目
    while(~scanf("%lld%lld%lld", &n,&x,&y))
    {
        memset(c, , sizeof(c));//初始化
        for(i = ;i < n; i++)
        {
            scanf("%lld", &num[i].val);
            num[i].pos = i + ;
        }
        sort(num, num+n, cmp);
        ans = ;
        for(i = ;i < n; ++i)//每一次插入目前最大值
        {
            update(num[i].pos);
            ans += sum(num[i].pos-);//統計前面有多少個數
        }
        ll anss=ans*min(x,y);
        printf("%lld\n",anss);
    }


}
           

【3】樹狀數組求逆序數（離散化）當maxn較大時，直接開數組顯然是不行了，這是的解決辦法就是離散化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll c[],s[],a[],b[];
ll n;
ll x,y;
int lowbit(int x)
{
    return x&(-x);
}
void update(ll i,int x)
{
    while(i<=n)
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}
ll Sum(ll x)
{
    ll sum=;
    while(x>)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    while(~scanf("%lld%lld%lld",&n,&x,&y))
    {
        memset(c,,sizeof(c));
        ll ans=;
        int m;
        for(int i=;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            a[i]+=;
            b[i]=a[i];
        }
        sort(b+,b+n+);
        int len=unique(b+,b+n+)-b-;
        for(int i=;i<=n;i++)
        {
            a[i]=lower_bound(b+,b+len+,a[i])-b;
            update(a[i],);
            ans+=(ll)i-Sum(a[i]);
        }
        ll ma=min(x,y);
        printf("%lld\n",ans*ma);
    }
}