HDU 1698 Just a Hook（线段树+简单lazy标记）

题目链接：Click here~~

题意：

最经典的区间染色入门问题。

初始时区间[1,n]的颜色都是1，之后有若干操作，改变某段区间的颜色，输出最后区间[1,n]的颜色之和。

解题思路：

主要说如何做lazy标记。

就是更新时，不更新到最底层（那样太浪费时间）。

对每一个节点，用一个标记记录这段区间是否是同一段颜色。

更新时，若当前节点正好是需要更新的区间，只要直接对这个节点改变标记即可。

若不是，则说明当前节点的区间大于需要更新的区间，此时如果直接改变标记会将那些不属于更新区间的点也改变了颜色。

做法是：将当前节点的标记传给它的两个儿子，并把自己的标记清空，然后再继续更新它的儿子区间，这样就解决了上面的问题。

而查询时，如果碰到有标记的节点，则可以不用继续递归，直接返回这段区间的颜色之和。

如果没有标记，则需要访问它的两个儿子，才能知道这段区间的颜色之和。

#include <stdio.h>

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

typedef __int64 LL;

const int M = 100003;

struct Tnode
{
    int l,r;
    int color;
}T[M<<2];

void Build(int u,int l,int r)
{
    T[u].l = l , T[u].r = r;
    if(l == r-1)
    {
        T[u].color = 1;
        return ;
    }
    int mid = MID(l,r);
    Build(L(u),l,mid);
    Build(R(u),mid,r);
    T[u].color = 0;
}

void Updata(int u,int l,int r,int up)
{
    if(T[u].color == up || T[u].l == l && T[u].r == r)
    {
        T[u].color = up;
        return ;
    }
    if(T[u].color)
    {
        T[L(u)].color = T[u].color;
        T[R(u)].color = T[u].color;
        T[u].color = 0;
    }
    int mid = MID(T[u].l,T[u].r);
    if(l >= mid)
        Updata(R(u),l,r,up);
    else
        if(r <= mid)
            Updata(L(u),l,r,up);
        else
        {
            Updata(L(u),l,mid,up);
            Updata(R(u),mid,r,up);
        }
}

int Query(int u,int l,int r)
{
    int mid = MID(T[u].l,T[u].r);
    if(T[u].l == l && T[u].r == r)
        if(T[u].color)
            return T[u].color*(r-l);
        else
            return Query(L(u),l,mid) + Query(R(u),mid,r);
    if(l >= mid)
        return Query(R(u),l,r);
    else
        if(r <= mid)
            return Query(L(u),l,r);
        else
            return Query(L(u),l,mid) + Query(R(u),mid,r);
}

int main()
{
    //freopen("in.ads","r",stdin);
    int n,z,Q,a,b,num;
    int ncase = 0;
    scanf("%d",&z);
    while(z--)
    {
        scanf("%d%d",&n,&Q);
        Build(1,1,n+1);
        while(Q--)
        {
            scanf("%d%d%d",&a,&b,&num);
            Updata(1,a,b+1,num);
        }
        printf("Case %d: The total value of the hook is %d.\n",++ncase,Query(1,1,n+1));
    }
    return 0;
}