给定一个 $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])

对于一个数$a[i]$,设其前面比它大的数有$bef[i]$个,发现每次冒泡排序都会使$bef[i]-1$,也就是说,对于$k$轮冒泡排序,我萌只需要求$\sum\limits_{bef[i] >= k+1}bef[i] - \sum\limits_{bef[i]>=k+1}k$,维护两个树状数组即可

#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;
}