线段树题目 zju1610

[知识点]线段树

1。创建线段树

2。对线段树着色

3。作相关统计

1。创建线段树

    1）取最小和最大的两个数作为端点，建立线段树

    2）当前节点的两个端点值之差等于一时，此时该节点即位叶子节点，不用再 向下分

    3）否则，分裂该节点为[a，(a + b) / 2], [(a + b) / 2, b];　

    4）创建线段树时，注意初始化操作

2。线段树着色（根据不同的题目此操作各不相同，对zju_1610做分析）

    1）当前节点的颜色与将要涂的颜色color相同，直接return

    2）当前线段树节点的两个端点和要涂的两个端点正好都相同，则将该节点着为color，然后return

    3）要涂的两个端点在当前节点的两个端点之间时：先将当前节点的颜色向其子节点扩展，然后：

       1.要涂的右端点小于或等于当前节点middle = (a + b) / 2时，向左子节点移动

       2.要涂的左端点大于或等于当前节点middle = (a + b) / 2时，向右子节点移动

       3.else （1 ，2）向左右子节点移动

3。相关统计

   1）当前节点未着色或其颜色与要统计的颜色不相同，直接return

   2）当前节点的颜色与要统计的颜色相同时：看标记p是否和当前节点的左端点相同，若相同说明此区间在上次已经统计过，则可直接执p为当前节点的右端点,然后return（p为标记已记录的有端点）/*PS:这一条总结的不是很好！有点冗余，不妨这样:

从0——8000依次扫描，如果还是原来的数，即还是一条颜色，那么continue，不计，是其他颜色，many[t]++;

即：一次扫描全部统计！非常漂亮！

*/

第一个线段树的代码：zju1610
#include<iostream>
using namespace std;

#define NOCOLOR -1
#define MUTILCOLOR -2
typedef struct seg
{
int color;//颜色
int ln;
int rn;//线段范围
struct seg * left;
struct seg * right;
}Seg;
int color[8001],many[8001];
Seg * Root=NULL;//声明一个线段数的根
Seg * Build(int left,int right)//建立二叉线段树
{
Seg *temp=(Seg *)malloc(sizeof(Seg));
temp->color=NOCOLOR;
temp->ln=left;
temp->rn=right;
if(right-left==1)
{  
   temp->left=NULL;
   temp->right=NULL;
}
else
{
   temp->left=Build(left,(left+right)>>1);
   temp->right=Build((left+right)>>1,right);
}
return temp;
}
void PutColor(Seg * s,int l,int r,int c)//开始打色
{
// if(s->color==c)
//   return ;
if(s->ln==l&&s->rn==r)
{
   s->color=c;
   return ;
}

int mid=(s->ln+s->rn)>>1;//中间数字
//注意，如果是大线段里面套小线段，即 线段的涂色将会混合，那么就需要特出处理一下咯
if(s->color!=MUTILCOLOR)
{
  
   s->left->color=s->color;
   s->right->color=s->color;
   s->color=MUTILCOLOR;
}
if(r<=mid)
{
   PutColor(s->left,l,r,c);
   return ;
}
if(l>=mid)
{
   PutColor(s->right,l,r,c);
   return;
}
PutColor(s->left,l,mid,c);
PutColor(s->right,mid,r,c);
}
void Caculator(Seg *temp)
{
// Seg * temp=Root;
if(temp->color!=MUTILCOLOR&&temp->color!=NOCOLOR)
{
   for(int i=temp->ln;i<temp->rn;i++)
   {
    color[i]=temp->color;
   }
}
if(temp->color==MUTILCOLOR)
{
Caculator(temp->left);
Caculator(temp->right);
}

}
void TotalCacular()
{
int t=-1;
for(int i=0;i<8000;i++)
{
   if(color[i]==t)
   continue;
   t=color[i];
   if(t!=-1)
   many[t]++;
}
}
int main()
{

int n;
while(scanf("%d",&n)!=EOF)
{
   Root=Build(0,8000);//建立线段数
   memset(color,-1,sizeof(color));
   memset(many,0,sizeof(many));
   int i;
   for(i=1;i<=n;i++)
   {
    int l,r,c;
    scanf("%d%d%d",&l,&r,&c);
    PutColor(Root,l,r,c);
   }
   Caculator(Root);
   TotalCacular();
   for(i=0;i<8000;i++)
   {
    if(many[i]>0)
    printf("%d %d\n",i,many[i]);
   }
   printf("\n");
}
return 1;
}