[セグメントツリーセグメント更新]hdoj 1698

タイトル:
1つの線分の値を修正し、[i,j]という区間の値を一度に1,2,または3に変更することができます.1---nこの区間の数字の和
 
考え方:
セグメント更新に対する理解を深めるテーマとして、セグメント更新に少しテクニックを加える必要があります.具体的にはコードupdate()を参照してください.

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 100010;
struct{
    int l, r, sum, lazy;
}node[3 * nMax];
int ans;
void build(int l ,int r ,int u){
    node[u].l = l;
    node[u].r = r;
    node[u].lazy = 1;
    if(l == r){
        node[u].sum = 1;
        return ;
    }
    int m = (l + r)>>1;
    build(l ,m ,u * 2);
    build(m+1 , r , u*2+1);
}

//lazy  0               ,    1
void update(int left ,int right , int val ,int u){
    if(node[u].lazy == val)return;
    if(left == node[u].l && right == node[u].r){
        node[u].lazy = val;
        return;
    }
    if(node[u].lazy != 0){
        //             ，   lazy          
        node[2*u].lazy = node[2*u+1].lazy = node[u].lazy;
        node[u].lazy = 0;
    }
    int m = (node[u].r + node[u].l)>>1;
    if(left <= m){
        update(left , min(right ,node[u*2].r), val, u*2);
    }
    if(right >= m+1){
        update(max(left ,m+1) , right , val, u*2 + 1);
    }
}
void query(int left ,int right ,int u){
    int l = node[u].l;
    int r = node[u].r;
    int w = right - left + 1;
    if(node[u].lazy != 0){
        ans += w*node[u].lazy;
        return;
    }
    int m = (r + l)>>1;
    if(right <= m){
        query(left , right , u*2);
        return;
    }
    if(left >= m+1){
        query(left , right , u*2+1);
        return;
    }
    query(left , m , u*2);
    query(m+1 , right , u*2 + 1);
}
int main(){
    int tcs,tt,n,m,a,b,c;
    scanf("%d",&tcs);
    for(tt = 1 ; tt <= tcs ; tt++){
        scanf("%d",&n);
        build(1 ,n ,1);
        scanf("%d",&m);
        while(m --){
            scanf("%d%d%d",&a,&b,&c);
            update(a ,b ,c ,1);
        }
        ans=0;
        query(1 , n ,1);
        printf("Case %d: The total value of the hook is %d.
",tt,ans);
//        printf("%d
",ans);
    }
    return 0;
}