学步园

http://acm.nyist.net/JudgeOnline/problem.php?pid=600

首先解释一个概念，什么叫离散化？

百度百科：将连续问题的解用一组离散要素来表征而近似求解的方法，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗一点的说，就是保持一种关系不变，把大数据转化为一些较小的数据处理，简化处理过程，但最终结果不改变的一种方法

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 100005
struct stu
{
	int num,id;   //id是用来记录初始的顺序
}s1[N];
int s2[N];
int s[N];
bool cmp(struct stu s1,struct stu s2)
{
	return s1.num<s2.num;
}
int lowbit(int k)
{
	return k&(-k);
}
void add(int k,int w)
{
	while(k<N)
	{
		s[k]+=w;
		k+=lowbit(k);
	}
}
int sum(int k)
{
	int p=0;
	while(k>0)
	{
		p+=s[k];
		k-=lowbit(k);
	}
	return p;
}
int main()
{
	int t,n,m,i,ans,count,k;
	scanf("%d",&t);
	while(t--)
	{
		memset(s,0,sizeof(s)); 
		scanf("%d%d",&n,&m);
		k=n<<1;
		ans=k+m;
		for(i=0;i<ans;i++)
		{
			scanf("%d",&s1[i].num);
			s1[i].id=i;
		}
		std::sort(s1,s1+ans,cmp);
		count=0;
		s2[s1[0].id]=++count;
		for(i=1;i<ans;i++)    //把大的数据转化为较小的数据，但数据间关系不变
		{
			if(s1[i].num!=s1[i-1].num)
				s2[s1[i].id]=++count;  			               else s2[s1[i].id]=count;
		}
		for(i=0;i<k;)
		{
			add(s2[i++],1);
			add(s2[i++]+1,-1);
		}
		for(i=k;i<ans;i++)
		{
			printf("%d\n",sum(s2[i]));
		}
	}
	return 0;
}