セグメントツリーの単点と区間の2つのツリー作成スキーム

線分ツリーには2つのツリー作成スキームがあります:1.単点区間【1,5】は、【1,3】【4,5】->【1,2】【3】【4】【5】(各区間の境界が隣接しておらず、各境界が1つの点)PS:線分が存在する場合は、線分を単点の形で表示し、例えば【1,2】区間は、左端点＋1を2とする点を単点とする形の線分木とすることができる.処理方式build(l,mid);build(mid+1,r); 2.線分は正常に理解すればよい.ただし、ツリーの作成時の終了条件はl=r-1であり、単位区間を示す.処理方式、build(l,mid);build(mid,r);
例題:Count the Colors ZOJ-1610(線分樹、区間被覆染色段数を求める)1.シングルポイントコード:

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn=1e4+7;
struct node
{
     
    int l,r,type;
} tree[maxn<<2];
int a[maxn];
int n,m;
void build(int x,int l,int r)
{
     
    tree[x].type=-1;
    tree[x].l=l,tree[x].r=r;
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}
void pushdown(int x)
{
     
    if(tree[x].type!=-1)
        tree[x<<1].type=tree[x<<1|1].type=tree[x].type,tree[x].type=-1;
}
void update(int x,int L,int R,int c)
{
     
    if(L<=tree[x].l&&R>=tree[x].r)
    {
     
        tree[x].type=c;
        return ;
    }
    if(tree[x].l==tree[x].r)return ;
    pushdown(x);
    int mid=(tree[x].l+tree[x].r)>>1;
    if(L<=mid)update(x<<1,L,R,c);
    if(R>mid)update(x<<1|1,L,R,c);
}
void query(int x)
{
     
    if(tree[x].l==tree[x].r)
    {
     
        if(tree[x].type!=m&&tree[x].type!=-1)
            a[tree[x].type]++;
        m=tree[x].type;
        return ;
    }
    pushdown(x);
    query(x<<1);
    query(x<<1|1);
}
int main()
{
     
    int i,j,x,y,c;
    while(~scanf("%d",&n))
    {
     
        m=-1;
        memset(a,0,sizeof(a));
        build(1,1,8000);
        for(i=1; i<=n; i++)
        {
     
            scanf("%d%d%d",&x,&y,&c);
            if(x<y)update(1,x+1,y,c);
        }
        query(1);
        for(i=0; i<8000; i++)
        {
     
            if(a[i])
                printf("%d %d
",i,a[i]);
        }
        printf("
");
    }
    return 0;
}

2.区間コード:

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn=1e4+7;
struct node
{
     
    int l,r,type;
} tree[maxn<<2];
int a[maxn];
int n,m;
void build(int x,int l,int r)
{
     
    tree[x].type=-1;
    tree[x].l=l,tree[x].r=r;
    if(l==r-1)
        return ;
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid,r);
}
void pushdown(int x)
{
     
    if(tree[x].type!=-1)
        tree[x<<1].type=tree[x<<1|1].type=tree[x].type,tree[x].type=-1;
}
void update(int x,int L,int R,int c)
{
     
    if(L<=tree[x].l&&R>=tree[x].r)
    {
     
        tree[x].type=c;
        return ;
    }
    if(tree[x].l==tree[x].r-1)return ;// ， ， 
    // ， 
    pushdown(x);                      // 0——1 ，mid=0， 
    // 0 （L=0，mid=0）
    int mid=(tree[x].l+tree[x].r)>>1;
    if(L<=mid)update(x<<1,L,R,c);
    if(R>mid)update(x<<1|1,L,R,c);//R=mid 
}
void query(int x)
{
     
    if(tree[x].l==tree[x].r-1)
    {
     
        if(tree[x].type!=m&&tree[x].type!=-1)
            a[tree[x].type]++;
        m=tree[x].type;
        return ;
    }
    pushdown(x);
    query(x<<1);
    query(x<<1|1);
}
int main()
{
     
    int i,j,x,y,c;
    while(~scanf("%d",&n))
    {
     
        m=-1;
        memset(a,0,sizeof(a));
        build(1,0,8000);
        for(i=1; i<=n; i++)
        {
     
            scanf("%d%d%d",&x,&y,&c);
            update(1,x,y,c);
        }
        query(1);
        for(i=0; i<=8000; i++)
        {
     
            if(a[i])
                printf("%d %d
",i,a[i]);
        }
        printf("
");
    }
    return 0;
}