[洛谷 6186][NOI Online 2020 提高组]冒泡排序

题目链接

https://www.luogu.com.cn/problem/P6186

题解

设 \(s_i=\sum_{j=1}^{i-1}[p_j \gt p_i]\)。

容易发现逆序对数就等于 \(\sum_{i=1}^n s_i\)。

这是没有排序的情况,经过一次排序后,逆序对数会怎样变化呢?

一个显然的事实是,一次冒泡排序后,设 \(p_j\) 为 \([1,i-1]\) 区间内最大的元素(且有 \(p_j \gt p_i\)),那么 \(p_j\) 一定会交换到 \(p_i\) 后面,而 \(p_i\) 会向前移动一位。

从而可以得到一个结论:对于那些满足 \(s_i \gt 0\) 的 \(i\),经过一次排序后会有 \(s_i=\max\{s_{i+1}-1,0\}\)。

这样,假如经历了 \(k\) 轮冒泡排序,只有那些满足 \(s_i \gt k\) 的 \(s_i\) 才能产生贡献(剩下的都变成零了)。

答案当然是:

$$\sum_{s_i \gt k}s_i -\sum_{s_i \gt k}k$$

这个可以用两个树状数组来维护。

修改操作就比较简单了。分类讨论邻位交换后 \(s_i\) 的变化情况即可。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
struct BIT
{
 long long a[200005];
 int lowbit(int x)
 {
  return x&(-x);
 }
 void init()
 {
  memset(a,0,sizeof(a));
 }
 void add(int x,int y)
 {
  if(x==0)return;
  while(x<=n)
  {
   a[x]+=y;
   x+=lowbit(x);
  }
 }
 long long query(int x)
 {
  long long ans=0;
  while(x)
  {
   ans+=a[x];
   x-=lowbit(x);
  }
  return ans;
 }
}tr1,tr2;
int a[200005],b[200005];
int main()
{
 cin>>n>>m;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i];
  b[i]=tr1.query(n)-tr1.query(a[i]);
  tr1.add(a[i],1);
 }
 tr1.init();
 for(int i=1;i<=n;i++)
  tr1.add(b[i],1),tr2.add(b[i],b[i]);
 while(m--)
 {
  int op,x;
  cin>>op>>x;
  if(op==1)
  {
   if(a[x]>a[x+1])
   {
    tr1.add(b[x+1],-1),tr2.add(b[x+1],-b[x+1]);
    b[x+1]--;
    tr1.add(b[x+1],1),tr2.add(b[x+1],b[x+1]);
   }
   else
   {
    tr1.add(b[x],-1),tr2.add(b[x],-b[x]);
    b[x]++;
    tr1.add(b[x],1),tr2.add(b[x],b[x]);
   }
   swap(a[x],a[x+1]),swap(b[x],b[x+1]);
  }
  else
  {
   if(x>=n)cout<<0<<endl;
   else
   {
    long long res1=(tr1.query(n)-tr1.query(x))*x;
    long long res2=tr2.query(n)-tr2.query(x);
    cout<<res2-res1<<endl;
   }
  }
 }
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注