題目鏈接：http://acm.buaa.edu.cn/problem/436/
題意：一個數列兩種操作：（1）將某個位置的數字改成另一個數字；（2）交換兩個位置的數字。每次操作之后輸出逆序數的個數。
思路：二維樹狀數組可以快速計算0<=i<=x,0<=j<=y內的數字之和。
int a[10005],c[105][10005];
int n,m,ans,C;int sum(int x,int y)
{int ans=0,i,j;for(i=x;i;i-=i&-i) for(j=y;j;j-=j&-j){ans+=c[i][j];}return ans;
}void add(int x,int y,int det)
{int i,j;for(i=x;i<=100;i+=i&-i) for(j=y;j<=n;j+=j&-j){c[i][j]+=det;}
}void change(int p,int x)
{add(a[p],p,-1);ans-=sum(100,p)-sum(a[p],p);ans-=sum(a[p]-1,n)-sum(a[p]-1,p);a[p]=x;add(a[p],p,1);ans+=sum(100,p)-sum(a[p],p);ans+=sum(a[p]-1,n)-sum(a[p]-1,p);
}int main()
{RD(C);while(C--){ans=0;clr(c,0);RD(n,m);int i,x,y,x1,y1;for(i=1;i<=n;i++){RD(a[i]);ans+=sum(100,i)-sum(a[i],i);add(a[i],i,1);}PR(ans);while(m--){RD(i,x,y);if(i==1){x1=a[x];y1=a[y];change(x,y1);change(y,x1);}else{change(x,y);}PR(ans);}}return 0;
}
