煎蛋

这道题其实非常简单 总体上三步走战略

第一步
离散化
第二步
建立映射
第三步
求逆序对
然后就ending了~
建议先做逆序对和树状数组1再来挑战这道题

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
const int mod = 1e8 - 3;

ll n ,a[maxn] ,b[maxn];
ll c[maxn] ,d[maxn] ,tree[maxn];
ll pos_b[maxn] ,p[maxn] ,ans = 0;

ll lowbit (ll x) {return x & -x;}
ll query (ll x)
{
    ll res = 0;
    while (x > 0)
    {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}
void add (ll x ,ll k)
{
    while (x <= n)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i] ,c[i] = a[i];
    for (int i = 1;i <= n;i++) cin >> b[i] ,d[i] = b[i];
    sort(c + 1 ,c + 1 + n);
    sort(d + 1 ,d + 1 + n);
    ll len1 = unique(c + 1 ,c + 1 + n) - (c + 1);
    ll len2 = unique(d + 1 ,d + 1 + n) - (d + 1);
    for (int i = 1;i <= n;i++) a[i] = lower_bound (c + 1 ,c + 1 + len1 ,a[i]) - c;
    for (int i = 1;i <= n;i++) b[i] = lower_bound (d + 1 ,d + 1 + len2 ,b[i]) - d;
    for (int i = 1;i <= n;i++) pos_b[b[i]] = i;
    for (int i = 1;i <= n;i++) p[i] = pos_b[a[i]];
    for (int i = 1;i <= n;i++)
    {
        ans += i - 1 - query (p[i]);
        ans %= mod;
        add (p[i] ,1);
    }
    cout << ans % mod << '\n';

    return 0;
}