题解 P5463 【小鱼比可爱（加强版）】

Frozencode · 2019-07-14 19:04:42 · 题解

考虑一组逆序对(a[i],a[j])贡献了几次,不难发现贡献了i*(n - j + 1)次。

考虑怎么统计，通常求逆序对我们是让树状数组上的值+1，现在我们实际上只要把+1改成+(n - j + 1)就行了（想想乘法分配律就知道这是对的）。

那么接下来就是常规的离散化加树状数组辣~

（答案会爆longlong,我偷懒写了个int128就欧克了QWQ)

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const ll maxn=1000010;
const ll INF=2147483647;
ll n,a[maxn],b[maxn],c[maxn],tot,res,f[maxn];
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}
ll lowbit(ll x)
{
    return x & (-x);
}
void update(ll x,ll det)
{
    while(x <= n)
    {
        f[x] += det;
        x += lowbit(x);
    }
    return;
}
ll qry(ll x)
{
    ll tem = 0;
    x--;
    while(x)
    {
        tem += f[x];
        x -= lowbit(x);
    }
    return tem;
}
int main()
{
    n = read();
    for(int i = 1;i <= n;i++)
    {
        a[i] = read();
        b[i] = a[i];
    }
    sort(b + 1,b + n + 1);
    tot = unique(b + 1,b + n + 1) - b - 1;
    for(int i = 1;i <= n;i++)
    {
        c[i] = lower_bound(b + 1,b + tot + 1,a[i]) - b;
    }
    for(int i = n;i >= 1;i--)
    {
        ll item = i;
        ll idet = n - i + 1;
        res += (ll)(item * qry(c[i]));
        update(c[i],idet);
    }
    write(res);
    return 0;
}