【线段树单点更新优化】H - Can you answer these queries? HDU - 4027

超、凢脫俗 2022-06-10 09:51 85阅读 0赞

Think:  
1知识点：线段树单点更新优化(优化条件(开根后平方数为1的结点不需要再次开根))  
2题意：两种操作：对一个区间所有数取其平方数；对一个区间所有数求和  
3反思：  
1>注意数据范围  
2>注意输入区间是否合法，是否L一定会小于R

[vjudge题目链接][vjudge]

以下为Time Limit Exceeded代码——未加优化条件

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    #define MID int mid = (l+r)/2
    #define lson rt<<1
    #define rson rt<<1|1
    
    typedef long long LL;
    
    const int N = 101400;
    
    struct Tree{
        LL sum;
    }tree[N<<2];
    
    void Build(int l, int r, int rt);
    void up_data(int rt);
    void up_v(int L, int R, int l, int r, int rt);
    LL Query(int L, int R, int l, int r, int rt);
    
    LL data[N];
    
    int main(){
        int k = 1, n, i, Q, q, L, R;
        while(~scanf("%d", &n)){
            printf("Case #%d:\n", k++);
            for(i = 1; i <= n; i++)
                scanf("%lld", &data[i]);
            Build(1, n, 1);
            scanf("%d", &Q);
            for(i = 0; i < Q; i++){
                scanf("%d %d %d", &q, &L, &R);
                if(L > R)
                    swap(L, R);
                if(q == 0)
                    up_v(L, R, 1, n, 1);
                else if(q == 1)
                    printf("%lld\n", Query(L, R, 1, n, 1));
            }
            printf("\n");
        }
        return 0;
    }
    void Build(int l, int r, int rt){
        if(l == r){
            tree[rt].sum = data[l];
            return;
        }
        MID;
        Build(l, mid, lson);
        Build(mid+1, r, rson);
        up_data(rt);
    }
    void up_data(int rt){
        tree[rt].sum = tree[lson].sum + tree[rson].sum;
    }
    void up_v(int L, int R, int l, int r, int rt){
    
        if(l == r){
            if(tree[rt].sum != 1)
                tree[rt].sum = sqrt(tree[rt].sum);
            return;
        }
        MID;
        if(L <= mid)
            up_v(L, R, l, mid, lson);
        if(R > mid)
            up_v(L, R, mid+1, r, rson);
        up_data(rt);
    }
    LL Query(int L, int R, int l, int r, int rt){
        if(L <= l && r <= R){
            return tree[rt].sum;
        }
        MID;
        LL cnt = 0;
        if(L <= mid)
            cnt += Query(L, R, l, mid, lson);
        if(R > mid)
            cnt += Query(L, R, mid+1, r, rson);
        return cnt;
    }

以下为Wrong Answer代码——输入数据中存在L > R 的情况

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    #define MID int mid = (l+r)/2
    #define lson rt<<1
    #define rson rt<<1|1
    
    typedef long long LL;
    
    const int N = 101400;
    
    struct Tree{
        LL sum;
    }tree[N<<2];
    
    void Build(int l, int r, int rt);
    void up_data(int rt);
    void up_v(int L, int R, int l, int r, int rt);
    LL Query(int L, int R, int l, int r, int rt);
    
    LL data[N];
    
    int main(){
        int k = 1, n, i, Q, q, L, R;
        while(~scanf("%d", &n)){
            printf("Case #%d:\n", k++);
            for(i = 1; i <= n; i++)
                scanf("%lld", &data[i]);
            Build(1, n, 1);
            scanf("%d", &Q);
            for(i = 0; i < Q; i++){
                scanf("%d %d %d", &q, &L, &R);
                if(q == 0)
                    up_v(L, R, 1, n, 1);
                else if(q == 1)
                    printf("%lld\n", Query(L, R, 1, n, 1));
            }
            printf("\n");
        }
        return 0;
    }
    void Build(int l, int r, int rt){
        if(l == r){
            tree[rt].sum = data[l];
            return;
        }
        MID;
        Build(l, mid, lson);
        Build(mid+1, r, rson);
        up_data(rt);
    }
    void up_data(int rt){
        tree[rt].sum = tree[lson].sum + tree[rson].sum;
    }
    void up_v(int L, int R, int l, int r, int rt){
        if(tree[rt].sum <= (r-l+1))
            return;
        if(l == r){
            if(tree[rt].sum != 1)
                tree[rt].sum = sqrt(tree[rt].sum);
            return;
        }
        MID;
        if(L <= mid)
            up_v(L, R, l, mid, lson);
        if(R > mid)
            up_v(L, R, mid+1, r, rson);
        up_data(rt);
    }
    LL Query(int L, int R, int l, int r, int rt){
        if(L <= l && r <= R){
            return tree[rt].sum;
        }
        MID;
        LL cnt = 0;
        if(L <= mid)
            cnt += Query(L, R, l, mid, lson);
        if(R > mid)
            cnt += Query(L, R, mid+1, r, rson);
        return cnt;
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    #define MID int mid = (l+r)/2
    #define lson rt<<1
    #define rson rt<<1|1
    
    typedef long long LL;
    
    const int N = 101400;
    
    struct Tree{
        LL sum;
    }tree[N<<2];
    
    void Build(int l, int r, int rt);
    void up_data(int rt);
    void up_v(int L, int R, int l, int r, int rt);
    LL Query(int L, int R, int l, int r, int rt);
    
    LL data[N];
    
    int main(){
        int k = 1, n, i, Q, q, L, R;
        while(~scanf("%d", &n)){
            for(i = 1; i <= n; i++)
                scanf("%lld", &data[i]);
            Build(1, n, 1);
            scanf("%d", &Q);
            printf("Case #%d:\n", k++);
            for(i = 0; i < Q; i++){
                scanf("%d %d %d", &q, &L, &R);
                if(L > R)
                    swap(L, R);
                if(q == 0)
                    up_v(L, R, 1, n, 1);
                else if(q == 1)
                    printf("%lld\n", Query(L, R, 1, n, 1));
            }
            printf("\n");
        }
        return 0;
    }
    void Build(int l, int r, int rt){
        if(l == r){
            tree[rt].sum = data[l];
            return;
        }
        MID;
        Build(l, mid, lson);
        Build(mid+1, r, rson);
        up_data(rt);
    }
    void up_data(int rt){
        tree[rt].sum = tree[lson].sum + tree[rson].sum;
    }
    void up_v(int L, int R, int l, int r, int rt){
        if(tree[rt].sum <= (r-l+1))
            return;
        if(l == r){
            if(tree[rt].sum != 1)
                tree[rt].sum = sqrt(tree[rt].sum);
            return;
        }
        MID;
        if(L <= mid)
            up_v(L, R, l, mid, lson);
        if(R > mid)
            up_v(L, R, mid+1, r, rson);
        up_data(rt);
    }
    LL Query(int L, int R, int l, int r, int rt){
        if(L <= l && r <= R){
            return tree[rt].sum;
        }
        MID;
        LL cnt = 0;
        if(L <= mid)
            cnt += Query(L, R, l, mid, lson);
        if(R > mid)
            cnt += Query(L, R, mid+1, r, rson);
        return cnt;
    }

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