Just a Hook

题目

给定一个区间[1,N]，里面的元素都是1，现在有M次区间修改的操作，每次会选择一个区间将其置为1或2，或3，问最后区间[1,N]的元素总和为多少？

分析

这是一道典型的区间覆盖问题，用线段树可以很好的解决。只需要在定义结点的时候，加上sum和tag就行。sum表示此结点对应区间的总和，tag表示要将其后代置为tag。tag = 1，2，3。所以pushdown和pushup就可以很容易想出来,具体看代码

AC代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
const ll maxn = 1e5+10;

ll T,N,M;
ll arr[maxn];
struct node{
    ll l,r,tag,sum;
}tr[4*maxn];
void pushup(ll u){
    node &fa = tr[u],&L = tr[u*2],&R = tr[u*2+1];
    fa.sum = L.sum + R.sum; //计算和简单加就可以了，因为加的时候其后代已经进行过pushdown操作了
}
void pushdown(ll u){
    node &fa = tr[u],&L = tr[u*2],&R = tr[u*2+1];
    if(fa.tag){ //如果要将后代置为tag
        L.sum = (L.r-L.l+1)*fa.tag; //重新计算和
        R.sum = (R.r-R.l+1)*fa.tag;
        L.tag = fa.tag; //后代传递
        R.tag = fa.tag;
        fa.tag = 0;
    }
}
void build(ll u,ll l,ll r){
    if(l == r){
        tr[u] = {l,r,1,1};
    }else{
        tr[u] = {l,r};
        ll mid = (l+r)>>1;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(u);
    }
}
void modify(ll u,ll l,ll r,ll tag){
    if(tr[u].l>=l && tr[u].r<=r){
        tr[u].sum = (tr[u].r-tr[u].l+1)*tag;
        tr[u].tag = tag;
    }else{
        pushdown(u);
        ll mid = tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u*2,l,r,tag);
        if(r>mid) modify(u*2+1,l,r,tag);
        pushup(u);
    }
}
ll query(ll u,ll l,ll r){
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
    else{
        pushdown(u);
        ll mid = tr[u].l+tr[u].r>>1;
        ll sum = 0;
        if(l<=mid) sum += query(u*2,l,r);
        if(r>mid) sum += query(u*2+1,l,r);
        pushup(u);
        return sum;
    }
}
int main(){
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%lld %lld",&N,&M);
        build(1,1,N);
        ll a,b,c;
        while(M--){
            scanf("%lld %lld %lld",&a,&b,&c);
            modify(1,a,b,c);
        }
        printf("Case %d: The total value of the hook is %lld.\n",++kase,query(1,1,N));
    }
    return 0;
}