UESTC 1583 曜酱的心意 树状数组求逆序数

曜酱的心意 树状数组求逆序数

Source

17暑假前集训-数据结构专题 By AutSky_JadeK

2017 UESTC Training for Data Structures

UESTC 1583 曜酱的心意

My Solution

题意：给出2个序列，问从一个序列到另一个序列需要的最少交换次数。

树状数组求逆序数
先读入ai，然后标记f[ai] = i;//1~n
然后读入bi的时候，直接记录 x[i] = f[b[i]]；
然后对于x[i]数组，从后到前，依次
_rank[i] = get[x[i]];
add(x[i], 1);
这样就可以求出所有的逆序数
复杂度 O(nlogn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;

int f[MAXN], a[MAXN];
//
int Tree[MAXN];
inline int lowbit(int x)
{
    return (x & -x);
}
inline void add(int x, int value)
{
    for(int i = x; i < MAXN; i += lowbit(i)){
        Tree[i] += value;
    }
}
inline int get(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i)){
        res += Tree[i];
    }
    return res;
}

int main()
{
    #ifdef LOCAL
    freopen("e.txt", "r", stdin);
    //freopen("e.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, i, x;
    LL ans = 0;
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        scanf("%d", &x);
        f[x] = i;
    }
    for(i = 1; i <= n; i++){ scanf("%d", &x); a[i] = f[x]; } for(i = n; i >= 1; i--){
        ans += get(a[i]);
        add(a[i], 1);
    }
    cout << ans << endl;

    #ifdef LOCAL
    memset(Tree, 0, sizeof Tree);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}