逆序数——树状数组

POJ 2299：求逆序数

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 63215		Accepted: 23579

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

Sample Output

6
0

Source

Waterloo local 2005.02.05

分析：

树状数组求逆序数相比归并排序要简单多了，例如：

4 3 2 1：

程序：

很容易看出，是求当前的数值，之前，有多少个比他小的，反着，这个数的逆序就是 i - sum(a[i])；

注意：树状数组A[] 从 1 出发，不然会死循环。

到了这里，大概思路已经清晰了，但是数组开不了这么大，怎么办呢？——离散化

例如：

9 19 27 36... ... 99999999999999999

数字很大，但个数不多，于是离散化。

离散化的操作是：每个数字有两个属性，一个是值，一个是原来的下标。按照值排序。

re[原来的下标] = 现在的下标。

这样，下标和值的信息都不会丢失。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 5000005;

int C[maxn];
int n;
int lowbit(int x) {
    return x&-x;
}


// A[1] + A[2] + ... + A[x]
int sum(int x) {
    int ret = 0;
    while(x>0) {
        ret+=C[x];
        x-=lowbit(x);
    }
    return ret;
}

// A[x] += d
void add(int x,int d) {
    while(x<=n) {
        C[x] +=d;
        x += lowbit(x);
    }
}


struct Node {
    int val;
    int pos;
    bool operator < (const Node &rhs) const {
        return val < rhs.val;
    }

}nodes[maxn];

int reflect[maxn];

int main() {

    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n),n) {
        memset(C,0,sizeof(C));
        long long cnt = 0;

        for(int i = 1; i<= n; i++) {
            scanf("%d",&nodes[i].val);
            nodes[i].pos = i;
        }

        sort(nodes+1,nodes+1+n);

        for(int i = 1; i <= n; i++)
            reflect[nodes[i].pos] = i;

        for(int i = 1; i <= n; i++) {
            add(reflect[i],1);
            cnt += (i-sum(reflect[i]));
        }

        printf("%lld
",cnt);
    }

    return 0;
}

BZOJ 4989

上下有两个位置分别对应的序列A、B，长度为n，

两序列为n的一个排列。当Ai == Bj时，上下会连一条边。

你可以选择序列A或者序列B进行旋转任意K步，

如 3 4 1 5 2 旋转两步为 5 2 3 4 1。

求旋转后最小的相交的线段的对数。

这里有两个序列：ab

初始化：从后往前，b 数组连上去，对饮的位置前面有多少已经连了。

然后是移动，对于ab数组都会移动，例如移动a数组：

a 数组数字在b上的位置，前面的数字都会香蕉，他移动到最后面后，后来的也一定会香蕉。

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int maxn = 100006;
 
int lowbit(int x) {
    return x&-x;
}
 
ll ans,ans0,ans1,C[maxn];
int n;
 
// A[1] + A[2] + ... + A[x]
ll sum(int x) {
    ll ret = 0;
    while(x>0) {
        ret +=C[x];
        x -= lowbit(x);
    }
    return ret;
}
 
// A[x] +=d
void add(int x,int d) {
    while(x<=n) {
        C[x]+=d;
        x +=lowbit(x);
    }
}
 
int a[maxn],b[maxn];
int p1[maxn],p2[maxn];
 
int main()
{
    scanf("%d",&n);
    for(int i=1; i<= n; i++) {
        scanf("%d",&a[i]);
        p1[a[i]] = i;
    }
 
    for(int i=1; i<= n; i++) {
        scanf("%d",&b[i]);
        p2[b[i]] = i;
    }
 
 
    for(int i=n; i>=1; i--) {
        ans0+=sum(p1[b[i]]);
        add(p1[b[i]],1);
    }
 
    ans = ans1 = ans0;
    //printf("%lld",ans0);
 
    for(int i = 1; i <= n; i++) {
        ans0= ans0 -  p1[b[i]] + 1 + n -p1[b[i]];
        ans = min(ans0,ans);
    }
 
    for(int i=1;i<=n;i++){
        ans1=ans1-p2[a[i]]+1+n-p2[a[i]];
        ans=min(ans,ans1);
    }
 
    cout << ans <<endl;
 
    return 0;
}