题目链接
首先我们知道，将数列从左向右依次排开，设$f_i$表示$a_i$左侧有多少个比它大的数，那么逆序对总数就是$sumlimits_{i=1}^n f_i$。
观察/手玩数据可以发现，在某次冒泡排序的过程中，第$k$轮向右移动的数，都具有$f_i=k-1$的性质。
深入观察一下，我们发现，这些数也仅仅会在第$k$轮向右移动，而有一些数就算到了第$k$轮也不会向右移动。
那么在向右移动之前，我们发现，它们都会向左移动一位，而每当有一对数交换位置，意味着整个序列的逆序对减一。
也就是说，直到第$k$轮为止，这些数在每一轮都会经历一次逆序对减一。
那我们可以将每轮会经历逆序对减一的数的个数写下来，每次询问求个前缀和就可以了。修改的话因为只会涉及一对逆序对，也很好做，只需要相应地延长或者缩短更小的那个数起作用的轮数就好了。
设$g_k=sumlimits_{forall i,f_i=k-1}1$，逆序对总数为$tot$。
由于树状数组lowbit的性质，我们只能从第一位开始。
令$s_1=tot$，$s_{k+1}=-(n-sumlimits_{t=1}^k g_t)$。
询问第$k$轮，就用树状数组求$sumlimits_{i=1}^{k+1}s_i$即可。
代码（100分）：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<queue> #include<map> #include<set> #define IL inline #define RG register #define _1 first #define _2 second using namespace std; typedef long long LL; const int N=2e5; int n,m,a[N+3],b[N+3]; int f[N+3],g[N+3]; LL sum[N+3]; IL int lowbit(int x){ return x&(-x); } IL void add(int p,LL x){ for(;p<=n;p+=lowbit(p)){ sum[p]+=x; } } IL LL pre(int p){ LL ret=0; for(;p>0;p-=lowbit(p)) ret+=sum[p]; return ret; } IL void init(){ LL tot=0; memset(sum,0,sizeof sum); memset(g,0,sizeof g); for(int i=1;i<=n;i++){ f[i]=i-1-pre(a[i]); tot+=f[i]; g[f[i]]++; add(a[i],1); }//算f和g数组 memset(sum,0,sizeof sum); add(1,tot); LL cnt=0; for(int i=0;i<n;i++){ cnt+=g[i]; add(i+2,-(n-cnt)); }//叠加树状数组 } IL void sol(){ int t,c; scanf("%d%d",&t,&c); if(t==1){ if(a[c]<a[c+1]){ add(1,1);//总逆序对增加 add(f[c]+2,-1);//f[c]增加了，就会延后a[c]的有影响轮数 f[c]++;//修改数值；g可以不修改，因为用不上了 swap(a[c],a[c+1]); swap(f[c],f[c+1]); }//a[c]>a[c+1] else { add(1,-1);//总逆序对减少 f[c+1]--;//f[c+1]减少了 add(f[c+1]+2,1);//就会缩减a[c+1]的有影响轮数 swap(a[c],a[c+1]); swap(f[c],f[c+1]); } } else printf("%lld ",pre(min(c,n-1)+1)); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); init(); while(m--) sol(); return 0; }