逆序对

火柴排队

/* 火柴排队
 * Au: GG
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 200000 + 3;
const int MOD = 99999997;

int n, c[N], d[N];
ll ans;

struct node {
    int num, pos;
    bool operator < (const node &x) const {
        return num < x.num;
    }
} a[N], b[N];

inline int lowbit(int x) {
    return x & (-x);
}
inline void modify(int x, int val) {
    while (x <= n) {
        d[x] += val; x += lowbit(x);
    }
}
inline ll query(int x) {
    ll sum = 0;
    while (x) {
        sum += d[x]; x -= lowbit(x);
    }
    return sum;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i].num), a[i].pos = i;
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i].num), b[i].pos = i;
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++)
        c[b[i].pos] = a[i].pos;
    for (int i = 1; i <= n; i++) {
        modify(c[i], 1);
        ans = (ans + i - query(c[i])) % MOD;
    }
    printf("%lld
", ans);
    return 0;
}