E - Just a Hook HDU - 1698——线段树区间更新+lazy标记

淡淡的烟草味﹌ 2022-06-10 04:40 164阅读 0赞

Think:  
1知识点：线段树区间更新+lazy标记  
2题意：在n个初始化点权为1的点的基础上进行区间更新，询问最终状态n个点的点权之和  
3反思：当前题目lazy标记赋值更新

[vjudge题目链接][vjudge]

以下为Wrong Answer代码——lazy标记更新错误

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 101400;
    
    struct Node{
        int sum;
    }node[N<<2];
    
    int lazy[N<<2];
    
    void Build(int l, int r, int rt);
    void Updata(int rt);
    void down(int rt, int l, int r);
    void up_v(int L, int R, int v, int l, int r, int rt);
    
    int main(){
        int T, k = 1, n, m, L, R, v;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            Build(1, n, 1);
            scanf("%d", &m);
            while(m--){
                scanf("%d %d %d", &L, &R, &v);
                up_v(L, R, v, 1, n, 1);
            }
            printf("Case %d: The total value of the hook is %d.\n", k++, node[1].sum);
        }
        return 0;
    }
    void Build(int l, int r, int rt){
        lazy[rt] = 0;
        if(l == r){
            node[rt].sum = 1;
            return;
        }
        int mid = (l+r)/2;
        Build(l, mid, rt<<1);
        Build(mid+1, r, rt<<1|1);
        Updata(rt);
    }
    void Updata(int rt){
        node[rt].sum = node[rt<<1].sum + node[rt<<1|1].sum;
    }
    void up_v(int L, int R, int v, int l, int r, int rt){
        if(L <= l && r <= R){
            node[rt].sum = v*(r-l+1);
            lazy[rt] = v;
            return;
        }
        down(rt, l, r);
        int mid = (l+r)/2;
        if(L <= mid)
            up_v(L, R, v, l, mid, rt<<1);
        if(R > mid)
            up_v(L, R, v, mid+1, r, rt<<1|1);
        Updata(rt);
    }
    void down(int rt, int l, int r){
        if(lazy[rt]){
            lazy[rt<<1] += lazy[rt];
            lazy[rt<<1|1] += lazy[rt];
            int mid = (l+r)/2;
            node[rt<<1].sum = lazy[rt]*(mid-l+1);
            node[rt<<1|1].sum = lazy[rt]*(r-mid);
            lazy[rt] = 0;
        }
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 101400;
    
    struct Node{
        int sum;
    }node[N<<2];
    
    int lazy[N<<2];
    
    void Build(int l, int r, int rt);
    void Updata(int rt);
    void down(int rt, int l, int r);
    void up_v(int L, int R, int v, int l, int r, int rt);
    
    int main(){
        int T, k = 1, n, m, L, R, v;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            Build(1, n, 1);
            scanf("%d", &m);
            while(m--){
                scanf("%d %d %d", &L, &R, &v);
                up_v(L, R, v, 1, n, 1);
            }
            printf("Case %d: The total value of the hook is %d.\n", k++, node[1].sum);
        }
        return 0;
    }
    void Build(int l, int r, int rt){
        lazy[rt] = 0;
        if(l == r){
            node[rt].sum = 1;
            return;
        }
        int mid = (l+r)/2;
        Build(l, mid, rt<<1);
        Build(mid+1, r, rt<<1|1);
        Updata(rt);
    }
    void Updata(int rt){
        node[rt].sum = node[rt<<1].sum + node[rt<<1|1].sum;
    }
    void up_v(int L, int R, int v, int l, int r, int rt){
        if(L <= l && r <= R){
            node[rt].sum = v*(r-l+1);
            lazy[rt] = v;
            return;
        }
        down(rt, l, r);
        int mid = (l+r)/2;
        if(L <= mid)
            up_v(L, R, v, l, mid, rt<<1);
        if(R > mid)
            up_v(L, R, v, mid+1, r, rt<<1|1);
        Updata(rt);
    }
    void down(int rt, int l, int r){
        if(lazy[rt]){
            lazy[rt<<1] = lazy[rt];/*lazy标记赋值更新*/
            lazy[rt<<1|1] = lazy[rt];/*lazy标记赋值更新*/
            int mid = (l+r)/2;
            node[rt<<1].sum = lazy[rt]*(mid-l+1);
            node[rt<<1|1].sum = lazy[rt]*(r-mid);
            lazy[rt] = 0;
        }
    }

[vjudge]: https://vjudge.net/contest/163011#problem/E