ABC261F 题解

题面

注意到如果两个球 \(i,j\) 有 \(i<j,x_i>x_j\)，那么这两个球一定会交换。

所以要交换 \(x\) 的逆序对数 次。

但是相同颜色交换没有代价，所以答案是 \(x\) 的逆序对数减去满足 \(c_i=c_j,i<j,x_i>x_j\) 的 \((i,j)\) 对的数量。

可以对每个 \(j\) 都求一遍满足 \(c_i=j\) 的 \(x_i\) 构成的 \(x'\) 的逆序对数，全部减去即可。

实现就直接树状数组就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3e5 + 5;
struct bit
{
    int a[N];
    void upd(int q, int v)
    {
        for(int i = q; i < N; i += (i & -i)) a[i] += v;
    }
    int qry(int q)
    {
        int ans = 0;
        for(int i = q; i; i -= (i & -i)) ans += a[i];
        return ans;
    }
} t;

int ans[N];
void calc(vector<pair<int, int>> v, int f)
{
    int s = 0;
    for(auto [i, p] : v)
    {
        ans[i] += f * (s - t.qry(p));
        s ++; t.upd(p, 1);
    }
    for(auto [i, p] : v) t.upd(p, -1);
}

int a[N], b[N], n;
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];
    vector<pair<int, int>> v;
    for(int i = 1; i <= n; i ++) v.push_back({i, b[i]});
    calc(v, 1);
    vector<pair<int, int>> u[N];
    for(int i = 1; i <= n; i ++)
        u[a[i]].push_back({i, b[i]});
    for(int i = 1; i <= n; i ++) calc(u[i], -1);
    ll s = 0;
    for(int i = 1; i <= n; i ++) s += ans[i];
    cout << s;

    return 0;
}