Frosh Week(HDOJ 3743)

Problem Description

During Frosh Week, students play various fun games to get to know each other and compete against other teams. In one such game, all the frosh on a team stand in a line, and are then asked to arrange themselves according to some criterion, such as their height, their birth date, or their student number. This rearrangement of the line must be accomplished only by successively swapping pairs of consecutive students. The team that finishes fastest wins. Thus, in order to win, you would like to minimize the number of swaps required.

Input

The first line of input contains one positive integer n, the number of students on the team, which will be no more than one million. The following n lines each contain one integer, the student number of each student on the team. No student number will appear more than once.

Output

Output a line containing the minimum number of swaps required to arrange the students in increasing order by student number.

Sample Input

3
3
1
2

Sample Output

2

My Code

这题就是求逆序对，除了树状数组线段树还可以用归并排序做。这个专题是树状数组，所以我还是用树状数组做。如果编号是从1到n的话这题就很简单，从前往后遍历，遇到数x，就标记一下a[x]，这时候数一下a[x~n]有几个数被标记，就说明有几个数是比x大，但排在了x的前面，即逆序。最后全部加起来就是答案。但这题编号不一定从1开始，可能很大，所以不能直接这么做，需要离散化，即将最小的数，变成1，第二大的数变成2，以此类推，保留相对大小不变的同时，将数据减小。

#include 
#include 
#include 
using namespace std;

struct node
{
    int id;   //id记录原位置
    int v;    //v记录值
} a[1000005]; //a数组用于离散化处理
int n;
int b[1000005];
bool cmp(node x, node y)
{
    return x.v < y.v;
}
int lowbit(int x)
{
    return x & -x;
}
int sum(int x)
{
    int ans = 0;
    while (x > 0)
    {
        ans += b[x];
        x -= lowbit(x);
    }
    return ans;
}
void update(int x, int v)
{
    while (x <= n)
    {
        b[x] += v;
        x += lowbit(x);
    }
}
long long ans;
int main()
{
    while (cin >> n)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].v;
            a[i].id = i;
        }
        sort(a + 1, a + n + 1, cmp); //按值大小排序
        ans = 0;
        for (int i = 1; i <= n; i++)
        {
            update(a[i].id, 1);      //按从小到大标记
            ans += i - sum(a[i].id); //如果b[i]到b[n]有n个标记，说明有n个比a[i].v小的数排在它后面
        }                            //全部加起来就总的逆序数
        cout << ans << endl;
    }
    return 0;
}