P1966 火柴排队

问题

P1966 [NOIP 2013 提高组] 火柴排队
两列火柴分别允许交换相邻位置，需要先让对应高度的平方差之和最小，再求达到这个最小值至少需要交换多少次。

数据规模：$n\le 10^5$，同一列内高度互不相同，单个高度可能接近 $2^{31}$。

我最开始的想法就是，既然要对应的高度的平方差之和最小，那不就直接把两个序列都从小到大排序就行了？

因为只能交换两个相邻的元素，显然直接就是求原序列的逆序对数量，那就可以用树状数组 / 归并排序来秒了。

但是这是不正确的，因为其实我们要做的，只是把两列排名相同的对应起来，不一定要都排序成 $1 \sim n$ 这种形式。

于是我想到了这一题 P1439 两个排列的最长公共子序列，将两列排名离散化后，得到他们各自的元素在原数列中的排名，然后映射后求逆序对即可。

对于 P1439 来说，是映射后求 LIS，而本题在映射后求逆序对。

▶

P1966

struct Disc { /* 模板代码略 */ } disc;
struct BIT { /* 模板代码略 */ } bit;

ll a[maxn], b[maxn];
int pos[maxn], c[maxn];
int ra[maxn], rb[maxn];

void solve( ) {
    int n = read( );

    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
        disc.add( a[i] ) ;
    }
    disc.init( );
    for( int i = 1; i <= n; ++ i ) {
        ra[i] = disc.get_idx( a[i] );
    }

    disc.clear( );
    for( int i = 1; i <= n; ++ i ) {
        b[i] = read( );
        disc.add( b[i] ) ;
    }
    disc.init( );
    for( int i = 1; i <= n; ++ i ) {
        rb[i] = disc.get_idx( b[i] );
    }

    for( int i = 1; i <= n; ++ i ) {
        pos[ra[i]] = i;
    }

    for( int i = 1; i <= n; ++ i ) {
        c[i] = pos[rb[i]];
    }

    bit.init( n );

    ll ans = 0;
    for( int i = 1; i <= n; ++ i ) {
        ans = ( ans + bit.ask( c[i] + 1, n ) ) % mod;
        bit.add( c[i], 1 );
    }
    cout << ans << '\n';
}

记录

• 归属：排列映射、离散化、逆序对。
• 真实修正：不能分别统计两列自身的逆序对；必须先按各自排名建立跨列对应关系，再统计相对排名排列的逆序对。
• 连接：P1439 映射后求 LIS，本题映射后求逆序对。
• 分类：待定。