题目描述
给定一个 1 ∼ n的排列 p_i，接下来有 m 次操作，操作共两种：
交换操作：给定 x，将当前排列中的第 x 个数与第 x+1 个数交换位置。
询问操作：给定 k，请你求出当前排列经过 k 轮冒泡排序后的逆序对个数。 对一个长度为 n 的排列 p_i 进行一轮冒泡排序的伪代码如下：
for i = 1 to n-1:
if p[i] > p[i + 1]:
swap(p[i], p[i + 1])
输入格式
第一行两个整数 n，m，表示排列长度与操作个数。
第二行 n 个整数表示排列 p_i。
接下来 m 行每行两个整数 t_i，c_i，描述一次操作：
若 t_i=1，则本次操作是交换操作，x=c_i；
若 t_i=2，则本次操作是询问操作，k=c_i。
输出格式
对于每次询问操作输出一行一个整数表示答案。
找规律
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=4e5+10;
#define int long long
int before[N],record[N],a[N],n,m;
int tree[N];
inline void add(int x,int y){
for(;x<=n;x+=x&(-x))tree[x]+=y;
}
inline int sum(int x){
int res=0;
for(;x;x-=x&(-x))res+=tree[x];
return res;
}
signed main(){
cin>>n>>m;
int tot=0;
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
before[i]=i-sum(a[i]);
tot+=before[i];
record[before[i]]++;
add(a[i],1);
}
memset(tree,0,sizeof(tree));
add(1,tot);
tot=0;
for(int i=0;i<n;i++){
tot+=record[i];
add(i+2,tot-n);
}
while(m--){
int opt,x;
scanf("%lld%lld",&opt,&x);
x=min(x,n-1);
if(opt==1){
x--;
if(a[x]<a[x+1]){
swap(a[x],a[x+1]);
swap(before[x],before[x+1]);
add(1,1);
add(before[x+1]+2,-1);
before[x+1]++;
}else{
swap(a[x],a[x+1]);
swap(before[x],before[x+1]);
add(1,-1);
before[x]--;
add(before[x]+2,1);
}
}else printf("%lld
",sum(x+1));
}
}