题目连接

题意：

一条长为N的铜链子，每个结点的价值为1。有两种修改，l,r,z;

z=2:表示把[l,r]区间内链子改为银质，价值为2.

z=3:表示把[l,r]区间内链子改为金质，价值为3.

思路：

线段树，区间重设，求和。

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=100000+10;

struct node

{

    int l;

    int r;

    int v;//标记该区间内的链条的属性，-1代表有杂色，1，2，3代表为纯色，并且属性值为；

};

node tree[maxn*4];

void maketree(int i,int l,int r)

{

    tree[i].l=l;

    tree[i].r=r;

    tree[i].v=1;起始为铜

    if(r==l)

        return ;

    int mid=(l+r)>>1;

    maketree(i<<1, l, mid);

    maketree(i<<1|1, mid+1, r);

}

void update(int i,int l,int r,int v)

{

    if(tree[i].v==v) //如果该区域内值一样则不用修改，以保证tree[i].l<=l,r<=tree[i].r;

        return ;

    if(tree[i].l==l&&tree[i].r==r)//如果区间与change区间一样则直接将tree[i].v=v;

    {

        tree[i].v=v;

        return ;

    }

    if(tree[i].v!=-1)//修改区间不一致，并且为纯色则，向下延伸

    {

        tree[i<<1].v=tree[i<<1|1].v=tree[i].v;//颜色向下分配

        tree[i].v=-1;//代表杂色

    }

    int mid=(tree[i].l+tree[i].r)>>1;

    if(l>=mid+1)

        update(i<<1|1, l, r, v);

    else if(r<=mid)

        update(i<<1, l, r, v);

    else

    {

        update(i<<1, l, mid, v);

        update(i<<1|1, mid+1,r,v);

    }

}

int sum(int i)

{

    if(tree[i].v!=-1)//叶子节点一定是纯色。

        return (tree[i].r-tree[i].l+1)*tree[i].v;

    return sum(i<<1)+sum(i<<1|1);

}

int main ()

{

    int T;scanf("%d",&T);

    int k=1;

    while(T--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        maketree(1,1,n);

        int l,r,v;

        for(int i=0;i<m;i++)

        {

            scanf("%d%d%d",&l,&r,&v);

            update(1, l, r, v);

        }

        printf("Case %d: The total value of the hook is %d.\n",k++,sum(1));

    }

    return 0;

}