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

· · 题解 

#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;
}