不知道什么是树状数组的 就先看看树状数组吧。。链接:点击打开链接;
看完之后 士兵杀敌(二) 应该就可以ac了。。
116 ac代码:
#include<stdio.h> int ok[1000001],end[1000001]={0}; int f(int a) { return a&(-a); } int main() { int a,b,c,d,n,m,i,j; int sum1,sum2; char ch[10]; scanf("%d%d",&n,&m); for(a=1;a<=n;a++) scanf("%d",&ok[a]); for(a=1;a<=n;a++) { b=f(a); for(c=a-b+1;c<=a;c++) end[a]+=ok[c]; } while(m--) { scanf("%s",ch); if(ch[0]=='A') { scanf("%d%d",&i,&j); while(i<=n) { end[i]+=j; i=i+f(i); } } else { scanf("%d%d",&i,&j); i=i-1; sum1=sum2=0; while(i>1) { sum1+=end[i]; i=i-f(i); } while(j>1) { sum2+=end[j]; j=j-f(j); } printf("%d\n",sum2-sum1); } } }
在看看Sort,,想想怎么用树状数组来ac。。设树状数组 c【10000】 和一般数组a【1000】;a【n】里存的是n出现的次数。。c【n】存的是。。你懂的。。
然后没输入一个数 计算一下逆序数,求和即可。。开始时 都为0;所以不用a【n】数组就可以了。。初始化c【n】为0即可。。
ac代码:
#include<stdio.h> #include<string.h> int c[1005]; int lowbit(int m) { return m&(-m); } void add(int m) { while(m<=1000) { c[m]+=1; m+=lowbit(m); } } int que(int m) { int sum=0; while(m>0) { sum+=c[m]; m-=lowbit(m); } return sum; } int main() { int a,b,n,m,k; scanf("%d",&k); while(k--) { int sum=0; memset(c,0,sizeof(c)); scanf("%d",&n); for(a=0;a<n;a++) { scanf("%d",&m); add(m); sum+=a-que(m-1); } printf("%d\n",sum); } }