树状数组：CDOJ1583-曜酱的心意（树状数组心得）

曜酱的心意

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 131072/131072KB (Java/Others)

Description

Chika说希望和我一起做学园偶像的时候，我真的很开心。——WatanabeYou

曜是千歌的青梅竹马，但是Aqours成立以后，千歌似乎总是与梨子在一起，而把曜冷落了。为了让千歌知晓自己的心意，曜酱决定做一件大事！她决定把一个给定的1~n的排列{a1,a2,…,an}（1≤ai≤n），且ai各不相同），用最少的交换次数，变换成另一个1~n的排列{b1,b2,…,bn}。并且，每次只交换相邻的两个元素。也许这样做了以后，千歌能更多地注意自己吧。曜这样想。

Input

第一行是一个整数n，第二行是一个长度为n的1~n的排列a，第三行是另一个长度为n的1~n的排列b。

Output

输出一行，一个整数，表示最少的交换次数。

Sample Input

4

2 3 1 4

3 2 1 4

3

3 2 1

1 2 3

Sample Output

1

3

解题心得：

关于树状数组其实弄的不是很懂，没办法看了好久了。反正树状数组用来求区间和很不错，能够用树状数组解决的基本都能够使用线段树解决。等把树状数组理解更深入了再来写博客。
求逆序数的方法有很多，比如归并排序，但本文重点讲一下如何用树状数组来求逆序数。

当数据的范围较小时，比如maxn=100000，那么我们可以开一个数组c[maxn],来记录前面数据的出现情况，初始化为0；当数据a出现时，就令c[a]=1。这样的话，　　欲求某个数a的逆序数，只需要算出在当前状态下c[a+1,maxn]中有多少个1，因为这些位置的数在a之前出现且比a大。但是若每添加一个数据a时，就得从a+1到　　　 maxn搜一遍，复杂度太高了。树状数组却能很好的解决这个问题，同样开一个数组d[maxn],初始化为0，d[i]记录下i结点所管辖范围内当前状态有多少个数；当添加数　　据a时，就向上更新d,这样一来，欲求a的逆序数时，只需要算sum(maxn)-sum(a)；sum(i)表示第i个位置之前出现了多少个1.　

　　举个例子：有5个数，分别为5 3 4 2 1，当读入数据a=5时，c为：0，0，0，0，1；d为：0，0，0，0，1；当读入数据a=3时，c为：0，0，1，0，1；d为：0，0 　　 1，1，1；当读入数据a=4时，c为：0，0，1，1，1；d为：0，0，1，2，1；…………。

此思想的关键在于，读入数据的最大值为maxn，由于maxn较小，所以可以用数组来记录状态。当maxn较大时，直接开数组显然是不行了，这是的解决办法就是离散　　化。所谓离散化，就是将连续问题的解用一组离散要素来表征而近似求解的方法，这个定义太抽象了，还是举个例子吧。

　　假如现在有一些数：1234 98756 123456 99999 56782,由于1234是第一小的数，所以num[1]=1;依此，有num[5]=2,num[2]=3,num[4]=4,num[3]=5;这　　样转化后并不影响原来数据的相对大小关系，何乐而不为呢！！！

还有一点值得注意，当有数据0出现时，由于0&0=0，无法更新，此时我们可以采取加一个数的方法将所有的数据都变成（引用树状数组求逆序数的分析）

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+100;

typedef long long ll;

ll num[maxn],ans[maxn];

ll n;

ll lowbit(int x)

{

    return x&-x;

}

void add(int x)

{

    while(x < maxn)

    {

        ans[x]++;

        x+=lowbit(x);

    }

}

ll sum(int x)

{

    ll Ans = 0;

    while(x > 0)

    {

        Ans += ans[x];

        x -= lowbit(x);

    }

    return Ans;

}

int main()

{

    while(scanf("%lld",&n) != EOF)

    {

        ll Ans = 0;

        memset(num,0,sizeof(num));

        memset(ans,0,sizeof(ans));

        for(int i=1;i<=n;i++)

        {

            int x;

            scanf("%d",&x);

            num[x] = i;//记录当前值出现的位置

        }

        for(int i=1;i<=n;i++)

        {

            int x;

            scanf("%d",&x);

            Ans += sum(n)-sum(num[x]-1);

            add(num[x]);

        }

        printf("%lld\n",Ans);

    }

    return 0;

}

巴特西