P6186 [NOI Online #1 提高组] 冒泡排序
littlechai
2021-04-19 20:56:42
给定一个 $1 ∼ n$ 的排列 $p_i$，接下来有 $m$ 次操作，操作共两种：
交换操作：给定 $x$，将当前排列中的第 $x$ 个数与第 $x+1$ 个数交换位置。
询问操作：给定 $k$，请你求出当前排列经过 $k$ 轮冒泡排序后的逆序对个数。
对一个长度为 $n$ 的排列 $p_i$ 进行一轮冒泡排序的伪代码如下：
```cpp
for i = 1 to n-1:
if p[i] > p[i + 1]:
swap(p[i], p[i + 1])
```
对于一个数$a[i]$,设其前面比它大的数有$bef[i]$个，发现每次冒泡排序都会使$bef[i]-1$,也就是说，对于$k$轮冒泡排序，我萌只需要求$\sum\limits_{bef[i] >= k+1}bef[i] - \sum\limits_{bef[i]>=k+1}k$,维护两个树状数组即可
```cpp
#include<bits/stdc++.h>
#define ll long long
#define ri register int
#define lowbit(x) x&(-x)
using namespace std;
const int INF = 2147483646;
const int p = 1e9+7;
const int maxn = 1e6+10;
int n, m;
ll a[maxn], bef[maxn];
struct tree{
ll cnt, val, num;
tree operator - (const tree x)const{
return (tree){cnt-x.cnt, val-x.val, num-x.num};
}
}z[maxn];
void add1(int x, ll k){
if(x == 0) return ;
while(x <= n){
z[x].cnt += k;
x += lowbit(x);
}
}
ll query1(int x){
ll res = 0;
while(x){
res += z[x].cnt;
x -= lowbit(x);
}
return res;
}
void add2(int x, int k, ll v){
if(x == 0) return ;
while(x <= n){
z[x].val += v;
z[x].num += k;
x += lowbit(x);
}
}
tree query2(int x){
ll sumb = 0, sumk = 0;
while(x){
sumb += z[x].val;
sumk += z[x].num;
x -= lowbit(x);
}
return (tree){0, sumb, sumk};
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++)
scanf("%lld",&a[i]);
for(int i = 1;i <= n;i ++){
ll k = i - query1(a[i]) - 1;
bef[i] = k;
add1(a[i], 1);
add2(k, 1, k);
}
while(m --){
ll op, x;
scanf("%lld%lld",&op,&x);
if(op == 1){
add2(bef[x], -1, -bef[x]);
add2(bef[x+1], -1, -bef[x+1]);
if(a[x] < a[x+1]) bef[x] ++;
else bef[x+1] --;
swap(a[x], a[x+1]);
swap(bef[x], bef[x+1]);
add2(bef[x], 1, bef[x]);
add2(bef[x+1], 1, bef[x+1]);
}
else{
if(x >= n){
printf("%d\n",0);
continue;
}
tree ans = query2(n) - query2(x);
printf("%lld\n",ans.val - 1ll*x*ans.num);
}
}
return 0;
}
```