涿州市网站建设,所有购物网站的名字,集团网站 wordpress,erp教学零基础入门题目链接#xff1a;http://acm.buaa.edu.cn/problem/436/ 题意#xff1a;一个数列两种操作#xff1a;#xff08;1#xff09;将某个位置的数字改成另一个数字#xff1b;#xff08;2#xff09;交换两个位置的数字。每次操作之后输出逆序数的个数。 思路#xff…题目链接http://acm.buaa.edu.cn/problem/436/ 题意一个数列两种操作1将某个位置的数字改成另一个数字2交换两个位置的数字。每次操作之后输出逆序数的个数。 思路二维树状数组可以快速计算0ix,0jy内的数字之和。 int a[10005],c[105][10005];
int n,m,ans,C;int sum(int x,int y)
{int ans0,i,j;for(ix;i;i-i-i) for(jy;j;j-j-j){ansc[i][j];}return ans;
}void add(int x,int y,int det)
{int i,j;for(ix;i100;ii-i) for(jy;jn;jj-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);anssum(100,p)-sum(a[p],p);anssum(a[p]-1,n)-sum(a[p]-1,p);
}int main()
{RD(C);while(C--){ans0;clr(c,0);RD(n,m);int i,x,y,x1,y1;for(i1;in;i){RD(a[i]);anssum(100,i)-sum(a[i],i);add(a[i],i,1);}PR(ans);while(m--){RD(i,x,y);if(i1){x1a[x];y1a[y];change(x,y1);change(y,x1);}else{change(x,y);}PR(ans);}}return 0;
}
