求逆序对

1.树状数组直接求逆序对¶

采用树状数组标记来求逆序对

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll a[100500]={0};
ll c[100500]={0};
ll maxn=10050,k,ans=0;
ll lowbit(ll x)
{
    return x&(-x);
}
ll add(ll k,ll x)
{
    for(ll i=k;i<=maxn;i+=lowbit(i))
        c[i]+=x;
}
ll getsum(ll k)
{
    ll ans=0;
    for(ll i=k;i>=1;i-=lowbit(i))
        ans+=c[i];
    return ans;
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&k);
        add(k,1);
        ans+=i-getsum(k);
    }
    printf("%d\n",ans);
}

2.离散化+树状数组求逆序对¶

http://icpc.upc.edu.cn/problem.php?cid=1422&pid=3

题目描述¶

“装满了鹅卵石的瓶子是满的吗？”墨老师曾经这样问过他的学生。“不是，因为还可以放入小石子、再放入细砂、最后再倒入水。”学生们回答。“那么从中可以得到什么启示呢？”墨老师又问，“启示我们时间总是可以挤出来的！”一个聪明的学生抢答。“你说得对！”墨老师微笑道，“但我还要告诉你们另一个重要经验，那就是：如果你不先将大的鹅卵石放进瓶子里去，你也许以后永远没机会再把它们放进去了。”

但这世上的很多人，做事却经常分不清事情的轻重缓急。我们可爱的典狱长大人就犯了这个错误，当他看到身高参差不齐的狱警们排成一列时，眉毛拧成了一个结，他最想知道的就是，到底有多少个狱警逆序排队了。这可以抽象为求逆序对的个数问题：即对于一个包含n个非负整数的数组A[1，…，n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ，A[ j] )为数组A中的一个逆序对。

例如，数组（3，1，4，5，2）的逆序对有(3，1)，(3，2)，(4，2)，(5，2)共4个。

输入¶

包括两行，第一行是一个整数n(1≤n≤1000)，表示狱警人数。第二行包含n个整数，用空格分隔，即每个狱警的身高，狱警身高均在int范围内。

输出¶

包括一行，这一行只包含一个整数，即逆序对的个数。

样例输入¶

5
3 1 4 5 2

样例输出¶

首先介绍一下离散化，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：原数据：1,999,100000,15；处理后：1,3,4,2；这样经过离散化处理后能够减少标记数组的范围，减少时间复杂度

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
struct node
{
    ll x;
    ll pos;
};
node a[100500]={0};
ll b[100500]={0};
ll c[100500]={0};
ll maxn=100005,k,ans=0;
ll lowbit(ll x)
{
    return x&(-x);
}
ll add(ll k,ll x)
{
    for(ll i=k;i<=maxn;i+=lowbit(i))
        c[i]+=x;
}
ll getsum(ll k)
{
    ll ans=0;
    for(ll i=k;i>=1;i-=lowbit(i))
        ans+=c[i];
    return ans;
}
bool cmp(node a,node b)
{
    return a.x<b.x;
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].x);
        a[i].pos=i;
    }
    sort(a+1,a+n+1,cmp);
    ll cnt=1;
    for(ll i=1;i<=n;i++)
    {
        if(i!=1&&a[i].x!=a[i-1].x)
            cnt++;
        b[a[i].pos]=cnt;
    }
    for(ll i=1;i<=n;i++)
    {
        add(b[i],1);
        ans+=i-getsum(b[i]);
    }
    printf("%lld\n",ans);
}

3.归并排序求逆序对¶

http://icpc.upc.edu.cn/problem.php?cid=2436&pid=0

题目描述¶

某正教授级特级教师获得了一段古老的文字，全部由 26 个大写英文字母组成。他产生了一个疯狂的想法，即想把这段文字中所有字母按 A 到 Z 的顺序排序，即所有 A 放在开头，然后跟着所有 B，再是所有 C，最后是所有 Z。比如原字符串为“HELLOWORLD”，排序后应变为“DEHLLLOORW”。但是特教毕竟领着国务院的特殊津贴，于是他还有一个要求，即排序时每次只能交换相邻两个字母。现在他想知道最少交换多少次能完成排序？

输入¶

仅一行，包含一个仅含大写字母的长度为 L 的字符串（注意 L 不输入）。

输出¶

共一行，包含一个整数表示最少交换次数。

样例输入¶

【样例1】 LSDSL 【样例2】 HELLOWORLD

样例输出¶

【样例1】 4 【样例2】 16

提示¶

对于50%的数据，1≤L≤2000；对于100%的数据，1≤L≤2×10^6

借用归并排序来求逆序对

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
char a1[2005000]="";
int a[2005000]= {0};
int b[2005000]= {0};
long long int merge_sort(long long int l,long long int r)
{
    if (l >= r)
        return 0;
    long long int mid = (l + r) >> 1, res = 0;
    res += merge_sort(l, mid);
    res += merge_sort(mid + 1, r);
    long long int i = l, j = mid + 1, cnt = 0;
    while (i <= mid && j <= r)
        if (a[i] <= a[j])
            b[cnt++] = a[i++];
        else
        {
            res += mid - i + 1;
            b[cnt++] = a[j++];
        }
    while (i <= mid)
        b[cnt++] = a[i++];
    while (j <= r)
        b[cnt++] = a[j++];
    for (long long int i = l, j = 0; j < cnt; ++i, ++j)
        a[i] = b[j];
    return res;
}
int main()
{
    scanf("%s",a1);
    for(long long int i=0; a1[i]; i++)
    {
        a[i]=a1[i]-'a';
    }
    long long int sum=merge_sort(0,strlen(a1)-1);
    cout<<sum<<endl;
    return 0;
}