[Leaf] [P5463] 小鱼比可爱

luogu-p5463-小鱼比可爱">Luogu-P5463 小鱼比可爱

1. 核心逻辑

• 问题本质: 求所有子区间的逆序对总数。

• 破局转换:

  1. 贡献思想：计算每个逆序对 $(i, j)$ 在多少个区间中出现。区间 $[L, R]$ 包含该对的条件是 $L \le i$ 且 $R \ge j$。

  2. 数学表达：对固定右端点 $j$，其贡献为 $\sum_{i < j, a_i > a_j} i \times (N - j + 1)$。

  3. 维护变更：BIT 维护的不再是“出现次数”，而是“比当前数大的那些数的下标之和”。

  4. 精度：答案可能极大，需使用 __int128。

2. 代码实现

▶

AcCode

// P5463 小鱼比可爱（加强版）
// Key Logic: BIT maintaining index sums for contribution calculation

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

const int maxn = 1e6 + 50;
int n;
int a[ maxn ], b[ maxn ];
ll c[ maxn ];
__int128 ans = 0;

void print( __int128 x )
{
    if( x > 9 ) print( x / 10 );
    putchar( ( int )( x % 10 ) + '0' );
}

int lowbit( int x )
{
    return x & -x;
}

void add( int x, int v )
{
    for( int i = x; i <= n; i += lowbit( i ) )
    {
        c[i] += v;
    }
}

ll query( int x )
{
    ll res = 0;
    for( int i = x; i; i -= lowbit( i ) )
    {
        res += c[i];
    }
    return res;
}

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

    cin >> n;
    ll total_idx_sum = 0;
    for( int i = 1; i <= n; ++ i )
    {
        cin >> a[i];
        b[i] = a[i];
    }

    sort( b + 1, b + n + 1 );
    int m = unique( b + 1, b + n + 1 ) - b - 1;

    for( int i = 1; i <= n; ++ i )
    {
        int rank = lower_bound( b + 1, b + m + 1, a[i] ) - b;
        total_idx_sum += i;
        add( rank, i );
        // 贡献：(当前总下标和 - 小于等于当前值的下标和) * (剩余可选右端点数)
        ans += ( __int128 )( total_idx_sum - query( rank ) ) * ( n - i + 1 );
    }

    if( ans == 0 ) putchar( '0' );
    else print( ans );
    putchar( '\n' );

    return 0;
}

3. 归档备注

• 这是一个非常漂亮的贡献法转化。

• BIT 维护下标和是解决此类“带权统计”问题的通用手段。

• 相关知识点：树状数组 | [[贡献法]]