NOIP 2013 火柴排队

很经典的一道题了,然而以前一直懒得做Orz
离散化+树状数组求逆序对

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

//define
const int maxn = 1e6 + 5;
const int mod =  99999997;
struct seg{
    int val, pos;
}a[maxn], b[maxn];
int n, ans, rev[maxn], dis[maxn];

inline cmp(seg x, seg y){return x.val < y.val;}

inline int lowbit(int x){return x & -x;}

inline void add(int x,int t){
    for(; x <= n; x += lowbit(x)){
        rev[x] += t;
        rev[x] %= mod;
    }
}

inline int sum(int x){
    int ans = 0;
    for(; x ; x -= lowbit(x)){
        ans += rev[x];
        ans %= mod;
    }
    return ans;
}

//main
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(register int i = 1; i <= n; ++i){
        cin >> a[i].val;a[i].pos = i;
    }
    for(register int i = 1; i <= n; ++i){
        cin >> b[i].val;b[i].pos = i;
    }
    
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + n + 1, cmp);

    for(register int i = 1; i <= n; ++i){
        dis[a[i].pos] = b[i].pos;
    }
    
    for(register int i = 1; i <= n; ++i){
        add(dis[i], 1);
        ans += i - sum(dis[i]);
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}
Tags:数据结构离散化树状数组
上一篇
没有啦~

添加新评论