NYOJ 322 Sort 和 NYOJ 116 士兵杀敌（二） 【树状数组】

原题链接：点击打开链接 322； 点击打开链接 116；

不知道什么是树状数组的 就先看看树状数组吧。。链接：点击打开链接；

看完之后 士兵杀敌（二） 应该就可以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);
	}
}