ARC194B题解

Awsdkl · 2025-03-13 16:48:57 · 题解

首先贪心地考虑（好吧我是看样例看出来的），按照数值从大到小的顺序来操作。即先将更大的数排到它应该去的位置。
然后我们考虑对于每一个数它产生的代价。对于第 i 个数，我们假设它最后会排到第 j 位。会发现，当我们要去操作这个数的时候，它会因为它左边的比它更大的数已经排到右边而向左移。我们设它左边的比它更大的数有 x 个，则它会产生的代价应该是 \cfrac{(i-x-1+j)\times |i-x-j|}{2}。这个式子是等差数列求和算出来的，其中首项应该是 j，末项是 i-x-1。
然后我们考虑 x 的求法。这其实就是一个求逆序对的求法，只不过固定了一个数，用线段树或者树状数组即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MAXN = 2e5+5;

ll n;
ll p[MAXN];
ll qd[MAXN]; //前面的大于 p[i] 的个数
pll ps[MAXN];
//树状数组
ll lowbit(ll x)
{
    return (x&(-x));
}

ll c[MAXN];

ll Sum(ll x)
{
    ll sum = 0;
    for(ll i = x;i > 0;i -= lowbit(i))
    {
        sum += c[i];
    }
    return sum;
}

void modify(ll x,ll k)
{
    for(ll i = x;i <= n;i += lowbit(i))
    {
        c[i] += k;
    }
    return;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%lld", &p[i]);
        qd[i] = Sum(n) - Sum(p[i]); 
        modify(p[i], 1LL);
        // 这两行就是计算在 p[i] 前面的大于 p[i] 的数的个数
        ps[i] = pll(p[i], i);
    }
    sort(ps + 1, ps + n + 1);
    ll ans = 0;
    for(int i = 1;i <= n;i++)
    {
        //ps[i].second 对应前文的 i
        //qd[ps[i].second] 对应前文的 x
        //i 对应前文的 j
        ll nowid = ps[i].second - qd[ps[i].second];
        ans += ((nowid-1 + i) * (ll)abs(nowid - i) >> 1LL);
    }
    printf("%lld", ans);

    return 0;
}