线段树题目 zju1610

原创文章,转载请注明出处.转载自: Li Haifeng's Blog
本文链接地址: 线段树题目 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为当前节点的右端点,然后returnp为标记已记录的有端点)/*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 %dn",i,many[i]);
   }
   printf("n");
}
return 1;
}

From Li Haifeng's Blog, post 线段树题目 zju1610

Post Footer automatically generated by wp-posturl plugin for wordpress.

分享到: