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;
    }