区间更新 求总区间——hdu1754

超时是因为底层结点也更新了，背离了区间更新的大原则，所以超时

#include<stdio.h>

struct data
{
    int l,r,val;
}st[300009];

inline int max(int a,int b)
{
    return a>b?a:b;
}
void build(int ll,int rr,int n)//½¨Ê÷
{
    st[n].l=ll;
    st[n].r=rr;
    st[n].val=1;
    if (ll==rr) return ;
    int mid=(ll+rr)/2;
    build(ll,mid,2*n);
    build(mid+1,rr,2*n+1);
}
void updata(int ll,int rr,int a,int n)//¸üнáµã
{
    if (st[n].l==ll&&st[n].r==rr&&ll==rr)
    {
        st[n].val=a;
        return ;
    }

    int mid=(st[n].l+st[n].r)/2;
    if (rr<=mid) updata(ll,rr,a,2*n);
    else if (ll>=mid+1) updata(ll,rr,a,2*n+1); 
    else
    {
        updata(ll,mid,a,2*n);
        updata(mid+1,rr,a,2*n+1);
    }
    st[n].val=st[n+n].val+st[n+n+1].val;//¸üÐÂÍ·½áµã
    
}

int main()
{
    int t;
    scanf("%d",&t);
    int add=0;
    while(t--)
    {
        add++;
        int n;
        scanf("%d",&n);

        build(1,n,1);
        int tt;
        scanf("%d",&tt);
        int i;
        //updata(1,n,1,1);
        for(i=1;i<=tt;i++)
        {
            int left,right,v;
            scanf("%d%d%d",&left,&right,&v);
            updata(left,right,v,1);
        }
        printf("Case %d: The total value of the hook is %d.\n",add,st[1].val);
    }
    return 0;
}

一段区间里为纯色时，val设为非-1，为杂色是val设为-1，可以加快查找更新

#include<stdio.h>

struct data
{
    int l,r,val;
}st[300009];

inline int max(int a,int b)
{
    return a>b?a:b;
}
void build(int ll,int rr,int n)//建树
{
    st[n].l=ll;
    st[n].r=rr;
    st[n].val=1;
    if (ll==rr) return ;
    int mid=(ll+rr)/2;
    build(ll,mid,2*n);
    build(mid+1,rr,2*n+1);
}
void updata(int ll,int rr,int a,int n)//更新结点
{
    if(st[n].val==a)return ;//值同，不需要更新

    if (st[n].l==ll&&st[n].r==rr)
    {
        st[n].val=a;
        return ;
    }

    if(st[n].val!=-1)//将纯色遗传到子代,父代变杂色
    {
        st[n+n].val=st[n].val;
        st[n+n+1].val=st[n].val;
        st[n].val=-1;
    }

    int mid=(st[n].l+st[n].r)/2;
    if (rr<=mid) updata(ll,rr,a,2*n);//在左子树则更新
    else if (ll>=mid+1) updata(ll,rr,a,2*n+1); //在右子树则更新
    else//左右树分开时
    {
        updata(ll,mid,a,2*n);
        updata(mid+1,rr,a,2*n+1);
    }
    
}

int search(int n)
{
    if(st[n].val!=-1)
    {
        return st[n].val*(st[n].r-st[n].l+1);
    }
    else
    {
        return search(n+n)+search(n+n+1);
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    int add=0;
    while(t--)
    {
        add++;
        int n;
        scanf("%d",&n);

        build(1,n,1);
        int tt;
        scanf("%d",&tt);
        int i;
        //updata(1,n,1,1);
        for(i=1;i<=tt;i++)
        {
            int left,right,v;
            scanf("%d%d%d",&left,&right,&v);
            updata(left,right,v,1);
        }
        printf("Case %d: The total value of the hook is %d.\n",add,search(1));
    }
    return 0;
}

还有一种枚举点，更新点的方法

#include<stdio.h>

struct data
{
    int l,r,val;
}qu[100009];

int main()
{
    int t,ci=0;
    scanf("%d",&t);
    while(t--)
    {
        ci++;
        int n;
        scanf("%d",&n);

        int all;
        scanf("%d",&all);
        int i,j;
        for(i=1;i<=all;i++)
        {
            int ll,rr,v;
            scanf("%d%d%d",&ll,&rr,&v);
            qu[i].l=ll;
            qu[i].r=rr;
            qu[i].val=v;
        }
        qu[0].val=1;

        int count=0;
        for(i=1;i<=n;i++)
        {
            for(j=all;j>=1;j--)
            {
                if(qu[j].l<=i&&i<=qu[j].r)
                {
                    break;
                }
            }
            count+=qu[j].val;
        }
        printf("Case %d: The total value of the hook is %d.\n",ci,count);
    }
}