hdu 1698 Just a Hook(线段树 - 区间修改 区间查询)

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

来源:hdu

  题意:给出一个N,区间中初始值为1,输出m代表m次修改,将区间[l,r]修改为v,输出最终这个序列的总和。

#include<bits/stdc++.h>
#define LNode x<<1
#define RNode x<<1|1
using namespace std;

typedef long long ll;
typedef pair<int,int>P;
const int Max_n=1e5+10;
const int inf=0x3f3f3f3f;
int sum[4*Max_n];int a[Max_n],tag[4*Max_n],Min[4*Max_n],cnt[Max_n*4];

void build(int l,int r,int x){//构建线段树(自顶向下)
    if(l==r){ sum[x]=a[l]; return ; }
    int mid=l+((r-l)>>1);
    build(l,mid,LNode);
    build(mid+1,r,RNode);
    sum[x]=sum[LNode]+sum[RNode];
    //build(1,n,1);//从根开始向上建立线段树
}
///区间最小值个数
/*void update(int x){//区间最小值的个数
    Min[x]=min(Min[LNode],Min[RNode]);
    if(Min[LNode]==Min[RNode]){
        Min[x]=Min[LNode];
        cnt[x]=cnt[LNode]+cnt[RNode];
    }else if(Min[LNode]<Min[RNode]){
        Min[x]=Min[LNode];
        cnt[x]=cnt[LNode];
    }else{
        Min[x]=Min[RNode];
        cnt[x]=cnt[RNode];
    }
}*/

void down(int l,int r,int x){//标记下传函数(延迟修改技术)
    int mid=l+(r-l)/2;
    if(tag[x]>0){//tag[x]!=0 区间加上某个数
        ///区间加上某个数
        //tag[LNode]+=tag[x];
        //tag[RNode]+=tag[x];
        ///区间加上某个数
        //sum[LNode]+=(mid-l+1)*tag[x];
        //sum[RNode]+=(r-mid)*tag[x];
        tag[LNode]=tag[RNode]=tag[x];
        sum[LNode]=(mid-l+1)*tag[x];
        sum[RNode]=(r-mid)*tag[x];
        tag[x]=0;
        ///区间最小值(区间最小值个数)
        //Min[LNode]+=tag[x];
        //Min[RNode]+=tag[x];
    }
}
///区间最小值个数查询
/*P query1(int A,int B,int l,int r,int x){
    if(A<=l&&B>=r) return P(Min[x],cnt[x]);//min和cnt都取出来
    down(l,r,x);
    int mid=l+(r-l)/2;
    P ans=P(inf,0);
    if(A<=mid) ans=min(ans,query1(A,B,l,mid,LNode));
    if(B>mid){
        P temp=min(ans,query1(A,B,mid+1,r,RNode));
        if(temp.first==ans.first) ans.second+=temp.second;
        else if(temp.first<ans.first) ans=temp;
    }
    return ans;
}*/

//线段树查询(自顶向下)
int query(int A,int B,int l,int r,int x){///区间查询和(log(n)))
    if(A<=l&&B>=r) return sum[x];
    down(l,r,x);//查询之前,检查是否要下传标记
    //(延迟修改技术,子节点不一定是正确的,但是当前结点一定是正确的)
    int mid=l+(r-l)/2,ans=0;
    ///维护区间最小值
    //int ans=0x3f3f3f3f
    //if(A<=mid) ans=min(ans,query(A,B,l,mid,LNode));
    //if(A<=mid) ans=min(ans,query(A,B,mid+1,r,RNode));
    if(A<=mid) ans+=query(A,B,l,mid,LNode);//查询左子树
    if(B>mid) ans+=query(A,B,mid+1,r,RNode);//查询右子树
    return ans;
}

//[A,B]:修改为v,[l,r]:当前结点对应的区间,x:当前结点
void change(int A,int B,int v,int l,int r,int x){///区间修改数据(log(n))
    if(A<=l&&B>=r) {
        tag[x]=v;
        sum[x]=v*(r-l+1);
        ///区间加上某个数
        //tag[x]+=v;
        //sum[x]+=v*(r-l+1);
        //Min[x]+=v;
        return ;
    }
    down(l,r,x);//修改之前,检查是否需要下传标记
    int mid=l+(r-l)/2;
    if(A<=mid) change(A,B,v,l,mid,LNode);
    if(B>mid) change(A,B,v,mid+1,r,RNode);
    sum[x]=sum[LNode]+sum[RNode];
    ///区间最小值
    //Min[x]=min(Min[LNode],Min[RNode]);
    ///区间最小值个数
    //update(x);
}

int main(){
    int T,Case=0;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n*4;i++) tag[i]=0;///多组输出tag数组清零
        for(int i=1;i<=n;i++) a[i]=1;
        build(1,n,1);
        while(m--){
            int l,r,v;
            scanf("%d%d%d",&l,&r,&v);
            change(l,r,v,1,n,1);
            //cout<<query(1,n,1,n,1);
        }
        printf("Case %d: The total value of the hook is %d.\n",++Case,query(1,n,1,n,1));
    }
    return 0;
}