C - A Simple Problem with Integers ——线段树_区间更新

浅浅的花香味﹌ 2022-06-11 08:28 124阅读 0赞

Think:  
1知识点：线段树-区间更新-区间查询-lazy标记  
2题意分析：区间更新+区间查询  
3反思：  
1>单点更新会超时  
2>lazy标记区间更新AC

[vjudge题目链接][vjudge]

以下为Time Limit Exceeded代码——单点更新整个区间超时

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    const int N = 101400;
    
    struct Node{
        LL num;
    }node[N<<2];
    
    void Build(int l, int r, int rt);
    void Updata(int rt);
    LL find(int L, int R, int l, int r, int rt);
    void add_v(int L, int R, int v, int l, int r, int rt);
    
    int main(){
        int n, m, L, R, v;
        char st[14];
        while(~scanf("%d %d", &n, &m)){
            Build(1, n, 1);
            while(m--){
                scanf("%s", st);
                if(st[0] == 'Q'){
                    scanf("%d %d", &L, &R);
                    printf("%lld\n", find(L, R, 1, n, 1));
                }
                else if(st[0] == 'C'){
                    scanf("%d %d %d", &L, &R, &v);
                    add_v(L, R, v, 1, n, 1);
                }
            }
        }
    }
    void Build(int l, int r, int rt){
        if(l == r){
            scanf("%lld", &node[rt].num);
            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].num = node[rt<<1].num + node[rt<<1|1].num;
    }
    LL find(int L, int R, int l, int r, int rt){
        if(L <= l && r <= R)
            return node[rt].num;
        int mid = (l+r)/2;
        LL sum = 0;
        if(L <= mid)
            sum += find(L, R, l, mid, rt<<1);
        if(R > mid)
            sum += find(L, R, mid+1, r, rt<<1|1);
        return sum;
    }
    void add_v(int L, int R, int v, int l, int r, int rt){
        if(l == r){
            node[rt].num += v;
            return;
        }
        int mid = (l+r)/2;
        if(L <= mid)
            add_v(L, R, v, l, mid, rt<<1);
        if(R > mid)
            add_v(L, R, v, mid+1, r, rt<<1|1);
        Updata(rt);
    }

以下为Accepted代码——lazy标记区间更新

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    const int N = 101400;
    
    struct Node{
        LL num;
    }node[N<<2];
    LL lazy[N<<2];/*lazy标记，用则更新*/
    
    void Build(int l, int r, int rt);
    void Updata(int rt);
    void down(int rt, int len);/*更新lazy数组标记的当前根节点的下一层*/
    LL find(int L, int R, int l, int r, int rt);
    void add_v(int L, int R, int v, int l, int r, int rt);
    
    int main(){
        int n, m, L, R, v;
        char st[14];
        while(~scanf("%d %d", &n, &m)){
            Build(1, n, 1);
            while(m--){
                scanf("%s", st);
                if(st[0] == 'Q'){
                    scanf("%d %d", &L, &R);
                    printf("%lld\n", find(L, R, 1, n, 1));
                }
                else if(st[0] == 'C'){
                    scanf("%d %d %d", &L, &R, &v);
                    add_v(L, R, v, 1, n, 1);
                }
            }
        }
    }
    void Build(int l, int r, int rt){
        lazy[rt] = 0;
        if(l == r){
            scanf("%lld", &node[rt].num);
            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].num = node[rt<<1].num + node[rt<<1|1].num;
    }
    void down(int rt, int len){
        if(lazy[rt]){
            lazy[rt<<1] += lazy[rt];
            lazy[rt<<1|1] += lazy[rt];
            node[rt<<1].num += lazy[rt]*(len - (len>>1));/*lazy[rt]*(l-mid+1)*/
            node[rt<<1|1].num += lazy[rt]*(len>>1);/*lazy[rt]*(l-(mid+1)+1)**/
            lazy[rt] = 0;
        }
    }
    LL find(int L, int R, int l, int r, int rt){
        if(L <= l && r <= R)
            return node[rt].num;
        down(rt, r-l+1);
        int mid = (l+r)/2;
        LL sum = 0;
        if(L <= mid)
            sum += find(L, R, l, mid, rt<<1);
        if(R > mid)
            sum += find(L, R, mid+1, r, rt<<1|1);
        return sum;
    }
    void add_v(int L, int R, int v, int l, int r, int rt){
        if(L <= l && r <= R){
            lazy[rt] += v;
            node[rt].num += v*(r-l+1);
            return;
        }
        down(rt, r-l+1);
        int mid = (l+r)/2;
        if(L <= mid)
            add_v(L, R, v, l, mid, rt<<1);
        if(R > mid)
            add_v(L, R, v, mid+1, r, rt<<1|1);
        Updata(rt);
    }

[vjudge]: https://vjudge.net/problem/POJ-3468