目录
显示
题目链接
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;
}