[Leaf] [P6186] [NOI Online #1 提高组] 冒泡排序

p6186-[noi-online-1-提高组]-冒泡排序---洛谷">P6186 [NOI Online #1 提高组] 冒泡排序 - 洛谷

1. 题面梗概

中译中: 给你一个排列，需要支持两个操作：

• 一是交换相邻的两个数；
• 二是这个排列如果丢进“冒泡排序”里跑 $k$ 轮，还剩多少个逆序对。

2. 逻辑推导

直觉分析：肯定不能去模拟冒泡，那样太慢了，我们得去分析冒泡排序中逆序对的变化情况。

在一轮冒泡中，每个数 $p_i$ 只要左边有比它大的数，它就会和左边的那个最大的数交换。

2.1 建模

• 我们定义 $c_i$ 为位置 $i$ 左侧比 $p_i$ 大的数的个数。显然，总逆序对数 $\sum c_i$。
• 冒泡：如果 $c_i > 0$，那么 $p_i$ 向前移动一位，就导致 $c_i - 1$。
• 结论：跑完 $k$ 趟冒泡后，原来的 $c_i$ 就会变成 $\max(0, c_i - k)$。

2.2 线段树

我们需要维护 $c_i$ 的集合，并支持以下几种操作：

1. 修改 $c_i$ 的值（交换 $p_{k}, p_{k+1}$）。
2. 查询 $\sum(c_i - k)$。

这个公式也可以拆解成：$\sum_{c_i > k}(c_i) - k \times cnt_i$。

那么我们可以建立一颗权值线段树，树的下标是 $c_i$ 的取值范围 $[0, n-1]$。每个节点维护两个信息：

1. cnt 在这个范围内的 $c_i$ 的数量。
2. sum 在这个范围内的 $c_i$ 的数值总和。

3. 代码实现

▶

AcCode

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

const int maxn = 2e5 + 5;

struct Info {
    ll cnt = 0, sum = 0;
    static Info merge( const Info& l, const Info& r ) {
        return { l.cnt + r.cnt, l.sum + r.sum };
    }
};

struct Node {
    int l, r;
    Info info;
} tr[maxn << 2];

#define ls (u << 1)
#define rs (u << 1 | 1)

void push_up( int u ) { 
    tr[u].info = Info::merge( tr[ls].info, tr[rs].info ); 
}

void build( int u, int l, int r ) 
{
    tr[u].l = l, tr[u].r = r;
    tr[u].info = { 0, 0 };
    if( l == r ) return;
    int mid = ( l + r ) >> 1;
    build( ls, l, mid );
    build( rs, mid + 1, r );
    push_up( u );
}

void modify( int u, int pos, int val ) 
{
    if( tr[u].l == tr[u].r )
    {
        tr[u].info.cnt += val;
        tr[u].info.sum += tr[u].l * val;
        return;
    }
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( pos <= mid ) modify( ls, pos, val );
    else modify( rs, pos, val );
    push_up( u );
}

Info query( int u, int l, int r ) 
{
    if( l > r ) return { 0 };
    if( l <= tr[u].l && tr[u].r <= r ) return tr[u].info;
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( r <= mid ) return query( ls, l, r );
    if( mid < l ) return query( rs, l, r );
    return Info::merge( query( ls, l, r ), query( rs, l, r ) );
}

int n, m;
int p[maxn];
int c[maxn];

struct Bit {
    int t[maxn];
    void add( int idx , int val ) {
        for( int i = idx; i <= n; i += i & -i ) t[i] += val;
    }
    ll query( int idx ) {
        ll res = 0;
        for( int i = idx; i; i -= i & -i ) res += t[i];
        return res;
    }
} bit;

void solve( )
{
    cin >> n >> m;
    build( 1, 0, n - 1 );

    for( int i = 1; i <= n; ++ i )
    {
        cin >> p[i];
        // c[i] = 当前位置比 p[i] 大的数的个数。
        c[i] = ( i - 1 ) - bit.query( p[i] );
        bit.add( p[i], 1 );
        // 将 c[i] 放入权值线段树
        modify( 1, c[i], 1 );
    }

    while( m -- )
    {
        int t, k;
        cin >> t >> k;
        if( t == 1 )
        {
	        // 交换操作，只影响 p[k] 和 p[k+1] 产生的 c 值 
            modify( 1, c[k], -1 );
            modify( 1, c[k + 1], -1 );
                
            // 交换后，只有这两者的相对大小决定了 c 的增减
            if( p[k] < p[k + 1] ) c[k] ++;
            else c[k + 1] --;

            swap( p[k], p[k + 1] );
            swap( c[k], c[k + 1] );

            modify( 1, c[k], 1 );
            modify( 1, c[k + 1], 1 );
        }
        else
        {
	        // 查询操作，统计 sum( max( 0 , c_i - k ) )。
            if( k >= n - 1 ) 
            {
                cout << 0 << '\n';
            }
            else 
            {
                Info res = query( 1, k + 1, n - 1 );
                cout << res.sum - k * res.cnt << '\n';
            }
        }
    }

}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve( );
    return 0;
}

4. 复盘

• 复杂度: $O( ( n + m ) \log n )$。

• 碎碎念:

  • 关键转换: 这道题最关键的地方在于对冒泡排序本质的理解，从而理解逆序对的变化过程，将动态模拟变成了静态权值维护。

  • 边界: 当 $k \ge n-1$ 时，冒泡排序一定已经完成，逆序对必然为 $0$，这个特判能规避线段树越界。

• 关联笔记: 线段树基础理论 | 树状数组 | 排序体系