HDU1698 Just a Hook （线段树lazy标记的运用）

快来打我* 2021-12-13 14:37 204阅读 0赞

## 题意：t组数据，给一个n，m表示n长度的钩和m次操作，初始钩子的每单位长度的价值为1，接下来输入 x,y,k 的操作把钩子\[x,y\]区间的价值替换为k,求m次操作后钩子的价值为多少 ##

## 分析：成段替换，最后只要求第一个区间就可以了，不用写query询问。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+5;
    int sum[maxn*4];
    int lazy[maxn*4];
    void up(int rt){
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    void down(int l,int r,int rt){
        if(!lazy[rt]) return;
        int mid=(l+r)>>1;
        lazy[rt<<1]=lazy[rt];lazy[rt<<1|1]=lazy[rt];
        sum[rt<<1]=lazy[rt]*(mid-l+1);
        sum[rt<<1|1]=lazy[rt]*(r-mid);
        lazy[rt]=0;
    }
    void build(int l,int r,int rt){
        sum[rt]=lazy[rt]=0;
        if(l==r){
            sum[rt]=1;
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,rt<<1);
        build(mid+1,r,rt<<1|1);
        up(rt);
    }
    void update(int L,int R,int k,int l,int r,int rt){
        if(L<=l&&r<=R){
            sum[rt]=k*(r-l+1);
            lazy[rt]=k;
            return;
        }
        down(l,r,rt);
        int mid=(l+r)>>1;
        if(L<=mid) update(L,R,k,l,mid,rt<<1);
        if(R>mid) update(L,R,k,mid+1,r,rt<<1|1);
        up(rt);
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        for(int cas=1;cas<=t;cas++){
            int n,m;
            scanf("%d%d",&n,&m);
            build(1,n,1);
            while(m--){
                int x,y,k;
                scanf("%d%d%d",&x,&y,&k);
                update(x,y,k,1,n,1);
            }
            printf("Case %d: The total value of the hook is %d.\n",cas,sum[1]);
        }
    }