题解 P6186 [NOI Online 提高组]冒泡排序

· · 题解

前言：这里有一只考场上以为打了20分部分分民间数据只有10分赛后100分的蒟蒻。

题目传送门：P6186 [NOI Online 提高组]冒泡排序

解题思路：

我们要做出这道题目，首先要发现冒泡排序的本质，我们知道冒泡排序外层循环最多跑 n-1 次（实际上是 n 次，只不过最后一次序列已经是有序的了，可以省去）。

例子：4 3 5 2 1

那么这个序列进行一次冒泡之后是这个样子的。

第一轮后：3 4 2 1 5

我们发现，4与3交换，5与2与1交换，但2却没有和1交换，所以一个数可以同自己右边的数进行交换当且仅当左边没有比它大的数，形象化为当你的左手边没有比你更强的人碾压你，你就可以一路向右碾压，直到碰到一个比你强的人，我们将此类数的状态称为可以碾压别人，非此类数称为不可碾压别人，这个就是冒泡排序的本质。

本质弄清了，我们还要处理的是，每次冒泡会减少多少逆序对，如果当前有 x 个可以碾压别人的数，则这 x 个数在此轮都不会被碾压，则有 n-x 个数会被碾压，逆序对就减少了 n-x 个。

所以当一个数前面有 y 个比它大的数的话，这个数会在第 y+1 轮冒泡中碾压别人。

用树状数组算出从未开始（第 1 轮）一直到第 n 次冒泡（第 n+1 轮）每一轮的逆序对个数，这个是初始化，即不进行交换的每轮冒泡的逆序对数。

进行交换的话如何修改？我们设数组 a 是每一个元素， 数组 b 是此元素前有几个比它大的元素。

如果 a_x < a_{x+1} ，那么交换 a 和 b 数组之后初始的逆序对个数就会 +1 ， b_{x+1} 也会 +1 也会但这个逆序对个数的 +1 会在什么时候失效呢？我们发现交换后 b_{x+1}+1 ，当交换前的 a_{x} 可以碾压别人的时候，也就是可以冒泡的时候，多出的逆序对就没有影响了，即在 b_{x+1}+1 前在树状数组中减去 1 ，为什么没有其他修改了呢？因为交换两个相邻的数只会影响一个逆序对，对前后的逆序对个数没有多余影响。

考虑这个序列：2 1 3

交换后面两个元素：2 3 1

当序列为：1 2 3的时候逆序对个数恢复原状。

如果 a_x > a_{x+1} ，那么交换 a 和 b 数组之后初始的逆序对个数就会 -1 ， b_{x} 也会 -1 也会但这个逆序对个数的 -1 会在什么时候失效呢？我们发现交换后 b_{x}-1 ，当交换后的 a_x 可以碾压别人的时候，也就是可以冒泡的时候，减去的逆序对个数就没有影响了，即在 b_{x}-1 后在树状数组中加上 1 ，为什么没有其他修改了呢？因为交换两个相邻的数只会影响一个逆序对，对前后的逆序对个数没有多余影响。

考虑这个序列：2 3 1

交换后面两个元素：2 1 3

当序列为：1 2 3的时候逆序对个数恢复原状。

也就是说比较交换前后的 a ，较小的在前面的 a 的 b 数组就是逆序对最早不产生影响的地方。

最后利用差分思想查询即可。

如果看一遍看不懂，请细品。

如果还是看不懂，建议思考交换后 a_x 前面的数对于后面的逆序对产生的影响。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,m,a[maxn],b[maxn],d[maxn];
long long c[maxn],ans;
inline int lowbit(int x){
    return x&(-x);
}
inline void update(int x,long long val){
    while(x<=n){
        c[x]+=val;
        x+=lowbit(x);
    }
}
inline long long getsum(int x){
    long long res=0;
    while(x>0){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
int main(){
    int opt,x,tmp=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        b[i]=i-1-getsum(a[i]);
        ans+=b[i],++d[b[i]];
        update(a[i],1);
    }
    memset(c,0,sizeof(c));
    update(1,ans);
    for(int i=0;i<n;++i){
        tmp+=d[i];
        update(i+2,-(n-tmp));
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d",&opt,&x);
        x=min(x,n-1);
        if(opt==1){
            if(a[x]<a[x+1]){
                swap(a[x],a[x+1]);
                swap(b[x],b[x+1]);
                update(1,1);
                update(b[x+1]+2,-1);
                b[x+1]++;
            }
            else{
                swap(a[x],a[x+1]);
                swap(b[x],b[x+1]);
                update(1,-1);
                b[x]--;
                update(b[x]+2,1);
            }
        }
        else printf("%lld\n",getsum(x+1));
    }
    return 0;
}