cqyz oj | 循环逆序对 | 逆序对 | 树状数组-布布扣-bubuko.com

　　0～n-1数字组成的序列,然后进行这样的操作,每次将最前面一个元素放到最后面去会得到一个序列,每得到一个序列都可得出该序列的逆序数（如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数）。要求求出最小的逆序数。

Input

输入包含若干组数据，每组数据包含两行，第一行为整数n，第二行是一个0..n-1的排列。

Output

每组数据输出一行一个整数，表示最小的逆序对数量。

Sample Input 1

10
1 3 6 9 0 8 5 7 4 2

Sample Output 1

Hint

n<=100 000

最多不超过10组数据.

逆序对的一种常规的做法就是归并排序，但是对于这道题，对n个序列进行n次归并排序，时间达到了O(n*n logn)，超时。

题目中说下一个序列是将这一个序列的第一个元素提到最后而成的，

容易发现这两个序列有很大部分逆序对是相同的，只有有关于改动的那个元素的逆序对变化了。

每次将a[1]放到最后，整个序列的逆序对增加了 b - l 对，

其中b是后面比a[1]大的元素个数，即新增的逆序对数量，

l是后面比a[1]小的元素个数，即减少的逆序对数量

求出b和l就能以O(1)的时间向下一个序列转移

可以用树状数组先求出a[i]的左边和右边分别有几个元素比a[i]小（l[i],r[i]），

那么a[i]左边比它大的个数就是dl[i]=i-1-l[i],右边比它大的个数就是dr[i]=n-i-r[i]

由a[1]开始依次计算出把每个元素提到最后之后序列的逆序对个数ans

则b = dl[i] + dr[i]，l = l[i] +r[i]

转移：ans = ans + (b - l)

　　= ans + (dl[i] + dr[i] - l[i] - r[i])

　　= ans + ( (i-1-l[i]) + (n-i-r[i]) - l[i] - r[i])

　　= ans + (n - 1 - 2*(l[i] + r[i]))

初始状态需要先计算出来：ans1 = sum(r[i]) 或者sum(i-1-l[i])

答案取ans的最小值即可

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
#define maxn 100005
#define maxm 100005
#define lowbit(x) (x&(-x))
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
int n, a[maxn];
int c[maxm];
int l[maxn], r[maxn];
void add(int p){
    while(p<=n) c[p]++, p += lowbit(p);
}
int query(int p){
    int ans = 0;
    while(p) ans += c[p], p -= lowbit(p);
    return ans;
}
int main(){
    while(scanf("%d",&n) == 1){
        FOR(i, 1, n) scanf("%d",&a[i]), a[i]++;
        memset(c, 0, sizeof(c)); FOR(i, 1, n) l[i] = query(a[i]-1), add(a[i]);
        memset(c, 0, sizeof(c)); ROF(i, n, 1) r[i] = query(a[i]-1), add(a[i]);
        ll ans = 0, tmp;
        FOR(i, 1, n) ans += r[i];
        tmp = ans;
        FOR(i, 1, n-1){
            tmp += n - 1 - 2 * (l[i] + r[i]);
            ans = min(ans, tmp);
        }
        printf("%lld\n", ans);
    }
    return 0;
}