[Leaf] [P1908] 逆序对

luogu-p1908-逆序对">Luogu-P1908 逆序对

1. 核心逻辑

• 问题本质: 求满足 $i < j$ 且 $a_i > a_j$ 的数对数量。

• 破局转换:

  1. 权值视角：按原序列顺序扫描。对于当前数 $a_i$，在它之前出现过且比它大的数都会与它构成逆序对。

  2. 离散化：由于值域较大（1e9），需通过排序+去重映射到 $1 \dots N$。

  3. 统计公式：$Ans += (i - 1 - \text{query}(rank[a_i]))$。

2. 代码实现

▶

AcCode

// P1908 逆序对
// Key Logic: Weight-based BIT with Discretization

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

const int maxn = 5e5 + 50;
int n;
int a[ maxn ], b[ maxn ], c[ maxn ];
ll ans = 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;
    }
}

int query( int x )
{
    int 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;
    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;
        ans += ( i - 1 - query( rank ) );
        add( rank, 1 );
    }

    cout << ans << endl;

    return 0;
}

3. 归档备注

• 树状数组最经典的应用场景。

• 离散化是处理大值域的核心前置步骤。

• 统计“比当前数大”的元素数量时，用“已处理总数 - 比当前数小或等的数量”是最稳妥的写法。

• 相关知识点：树状数组 | 降维技巧