题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1698

解题思路

区间修改，区间查询。
这个被查询的区间不是别人，正是全部1~n。
板子题，不会线段树可以看看专栏的第一篇题解内的线段树讲解链接。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long

using namespace std;

const int N=1e5+10;

struct TREE
{
    int l,r,lazy,sum;    
}tree[N<<2];
int T,n,q,x,y,z,cas;
void Build(int i,int l,int r)
{
    tree[i].l=l;
    tree[i].r=r;
    tree[i].lazy=0;
    tree[i].sum=0;
    if(tree[i].l==tree[i].r)
    {
        tree[i].sum=1;
        return ;
    }
    int mid=(l+r)>>1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    return ;
}
void PushDown(int i)
{
    if(tree[i].lazy==0) return ;
    tree[i<<1].lazy=tree[i].lazy;
    tree[i<<1|1].lazy=tree[i].lazy;
    tree[i<<1].sum=(tree[i<<1].r-tree[i<<1].l+1)*tree[i].lazy;
    tree[i<<1|1].sum=(tree[i<<1|1].r-tree[i<<1|1].l+1)*tree[i].lazy;
    tree[i].lazy=0;
    return ;
}
void Update(int i,int l,int r,int c)
{
    if(l<=tree[i].l && tree[i].r<=r)
    {
        tree[i].lazy=c;
        tree[i].sum=(tree[i].r-tree[i].l+1)*c;
        return ;
    }
    PushDown(i);
    if(tree[i<<1].r>=l) Update(i<<1,l,r,c);//left
    if(tree[i<<1|1].l<=r) Update(i<<1|1,l,r,c);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        cas++;
        scanf("%d%d",&n,&q);
        Build(1,1,n);
        while(q--)
        {
            scanf("%d%d%d",&x,&y,&z);
            Update(1,x,y,z);
        }
        printf("Case %d: The total value of the hook is %d.\n",cas,tree[1].sum);
    }
}