hdu（1556）Color the ball

本文主要是介绍hdu（1556）Color the ball，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一次用直接更新到节点的方法，结果果断超时。。唉。。

只有用更新区间的方法了；只要图的颜色在这个区间就可以加一，

这样使得增加的值都存在了区间最大的节点上，为了使其下达给下面各个节点，就用到了sum函数。

不过这样感觉还是慢啊，一千多毫秒。。

#include"stdio.h"
#include"string.h"
struct point
{
 int x,y,sum,s;
}a[400000];
void tree(int t,int x,int y)
{
 a[t].x=x;
 a[t].y=y;
 if(x==y)
 {
  a[t].sum=0;
  return ;
 }
 int temp=2*t;
 int mid=(x+y)/2;
 tree(temp,x,mid);
 tree(temp+1,mid+1,y);
 a[t].sum=a[temp].sum+a[temp+1].sum;
}
void find(int t,int x,int y)
{
 if(x<=a[t].x&&y>=a[t].y)//找到要涂颜色区间，这里很重要，表示用区间后再慢慢回归到子节点上
 {
  a[t].sum++;
  return;
 }
 int temp=2*t;
 int mid=(a[t].x+a[t].y)/2;
 if(y<=mid)
  find(temp,x,y);
 else if(x>mid)
  find(temp+1,x,y);
 else
 {
  find(temp,x,mid);
  find(temp+1,mid+1,y);
 }
}
void sum(int t)
{
 if(a[t].x==a[t].y)
 {
  a[a[t].x].s=a[t].sum;
  return ;
 }
 int temp=2*t;
 int mid=(a[t].x+a[t].y)/2;
 a[temp].sum+=a[t].sum;
 a[temp+1].sum+=a[t].sum;
 sum(temp);
 sum(temp+1);
}
int main()
{
 int m,n,i,j,k,h;
 while(scanf("%d",&m),m)
 {
  tree(1,1,m);
  for(i=1;i<=m;i++)
  {
   scanf("%d%d",&k,&h);
   find(1,k,h);
  }
  sum(1);
  for(i=1;i<m;i++)
   printf("%d ",a[i].s);
  printf("%d\n",a[m].s);
 }
 return 0;
}

这篇关于hdu（1556）Color the ball的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---