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

不错的思维题。

先考虑进行一轮冒泡排序的结果。我们发现，对于一个数，当且仅当它前面没有大于它的数，它的位置会被后移到第一个大于它的数，并且在之后的每一轮都会后移。并且每轮冒泡排序有 $k$ 个这样的数，那么这一轮减少的逆序对数量就是 $n-k$。更进一步，我们发现：若一个数前面有 $\le k$ 个大于它的数，那么它将在第 $k+1$ 轮冒泡排序时一定会被后移。

于是我们考虑预处理出 $pre_i$ 表示第 $i$ 个数前面有多少个大于它的数，这个很容易可以用树状数组来求。而逆序对个数就是 $\sum_{i=1}^{n} pre_i$。我们再用树状数组来维护 $k$ 轮冒泡排序进行完后的逆序对个数就行了。

对于修改操作也很简单，就是一个差分形式，直接单点修改就可以了。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

int n,m;
int a[N];
ll sum,c[N],pre[N],p[N];
inline int lowbit(int x)
{
    return x&(-x);
}
inline void add(int x,ll k)
{
    for(;x<=n;x+=lowbit(x))
        c[x]+=k;
}
inline ll ask(int x)
{
    ll res=0;
    for(;x;x-=lowbit(x))
        res+=c[x];
    return res;
}
int main()
{
    read(n,m);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        pre[i]=i-1-ask(a[i]);
        sum+=pre[i],p[pre[i]]++;
        add(a[i],1);
    }
    memset(c,0,sizeof(c));
    add(1,sum);
    int res=0;
    for(int i=0;i<n;i++)
    {
        res+=p[i];
        add(i+2,res-n);
    }
    for(int i=1;i<=m;i++)
    {
        int op,x;
        read(op,x);
        x=min(x,n-1);
        if(op==1)
        {
            swap(a[x],a[x+1]);
            swap(pre[x],pre[x+1]);
            if(a[x]<a[x+1])
            {
                add(1,-1);
                pre[x]--;
                add(pre[x]+2,1);
            }
            else
            {
                add(1,1);
                add(pre[x+1]+2,-1);
                pre[x+1]++;
            }
        }
        else printf("%lld\n",ask(x+1));
    }
    return 0;
}