hdu 1556 简单线段树

http://acm.hdu.edu.cn/showproblem.php?pid=1556

汉语题，不解释；

思路：此题是线段树的染色，先分段染色，可以nlogn级别，在算出每个位置的染色数；求染色数的时候，有两种方法

1， 用一个数记录step的值，之后除以2，把每个值相加，直到为一时结束；为从下向上寻找；

2，用递归，从上往下寻找；

下面是我的2代码；

#include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<math.h>
 #include<iostream>
 #include<algorithm>
 using namespace std;


 const int sizen=200000+100;//千万可用define定义这个表达式
 struct ele
 {
     int left;
     int right;
     int sum;
 }p[sizen*4];


 void build(int L,int R,int step)
 {
     p[step].left=L;
     p[step].right=R;
     if(L==R)
         p[step].sum=0;
     else
     {
         int Mid=(L+R)/2;
         build(L,Mid,2*step);
         build(Mid+1,R,2*step+1);
         p[step].sum=0;
     }
 }


 void update(int L,int R,int step)
 {
     if(p[step].left==L&&R==p[step].right)
         p[step].sum++;
     else
     {
         int Mid=(p[step].left+p[step].right)/2;
         if(R<=Mid)
             update(L,R,2*step);
         else
         if(L>=Mid+1)
             update(L,R,2*step+1);
         else
         {
             update(L,Mid,2*step);
             update(Mid+1,R,2*step+1);
         }
     }
 }


 int summ(int x,int step)
 {
     if(p[step].left==p[step].right)
         return p[step].sum;
     else
     {
         int Mid=(p[step].left+p[step].right)/2;
         if(x<=Mid)
             return summ(x,2*step)+p[step].sum;
         else
             return summ(x,2*step+1)+p[step].sum;
     }
 }


 int main()
 {
     int N;
     int x,y;
     int n;
     int i;
     while(scanf("%d",&N)&&N)
     {
         n=N;
         build(1,N,1);
         while(N--)
         {
             scanf("%d%d",&x,&y);
             update(x,y,1);
         }
         for(i=1;i<n;i++)
             printf("%d ",summ(i,1));
         printf("%d\n",summ(n,1));
     }
     return 0;
 }

这个是我的一代吗

#include<stdio.h>
 #include<string.h>
 int a[100002];
 int t[100002];
 struct ele
 {
     int left;
     int right;
     int value;
 }p[401111]; void build(int L,int R,int step)
 {
     p[step].left=L;
     p[step].right=R;
     if(L==R)
     {
         p[step].value=0;
         a[L]=step;
     }
     else
     {
         int Mid=(L+R)/2;
         build(L,Mid,2*step);
         build(Mid+1,R,2*step+1);
         p[step].value=0;
     }
 } void update(int L,int R,int step)
 {
     if(p[step].left==L&&p[step].right==R)
      {
          p[step].value++;
         // printf("%d\n",p[step].left);
      }
     else
     {
         int Mid=(p[step].left+p[step].right)/2;
         if(R<=Mid)
             update(L,R,2*step);
         else
         if(L>=Mid+1)
             update(L,R,2*step+1);
         else
         {
             update(L,Mid,2*step);
             update(Mid+1,R,2*step+1);
         }
     }
 } int main()
 {
     int n,i,j;
     int x,y;
     while(scanf("%d",&n),n)
     {
         build(1,n,1);
         for(i=1;i<=n;i++)
         {
             scanf("%d%d",&x,&y);
             update(x,y,1);
         }
         for(i=1;i<=n;i++)
         {
             j=0;
             while(a[i])
             {
                 j+=p[a[i]].value;
                 a[i]/=2;
             }
             if(i!=n)
                 printf("%d ",j);
             else
                 printf("%d\n",j);
         }
     }
     return 0;
 }

【转自：武汉网站开发 http://www.1234xp.com/wuhan.html 网络转载请说明出处】