首页 > 其他分享 >洛谷 p3372 线段树

洛谷 p3372 线段树

时间:2024-04-19 11:16:22浏览次数:21  
标签:Node sz 洛谷 int 线段 long lazyNode p3372 sum

更改了线段树实现的方式,将lazy值作为单独的节点存在,降低存储压力

struct Node{
    long long sum;
    Node():sum(0ll){}

    Node operator +(const Node& other){
        Node res = *this;
        res.sum += other.sum;
        return res;
    };

    void applyLazy(lazyNode& value, int length){
        this->sum += 1ll * value.add * length;
    }
};


template<typename T>
class SegmentTree{
public:
    SegmentTree(const vector<T>& s): sz_(int(s.size() - 1)){
        st_.resize(4 * sz_);
        lazy_.resize(4 * sz_);
        build(s, 1, 1, sz_);
    }

    void update(int i, int j, lazyNode value){
        update(1, 1, sz_, i, j, value);
    }

    long long query(int i, int j){
        return query(1, 1, sz_, i, j).sum;
    }


private:
    vector<T> st_;
    vector<lazyNode> lazy_;
    int sz_;
    const lazyNode flag_{};

    void update(int p, int l, int r, int i, int j, lazyNode value){
        propagate(p, l, r);
        if (i > j){
            return;
        }
        if (l >= i && r <= j){
            lazy_[p] = value;
            propagate(p, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(p << 1, l, mid, i, min(mid, j), value);
        update(p << 1 | 1, mid + 1, r, max(mid + 1, i), j, value);
        st_[p] = st_[p << 1] + st_[p << 1 | 1];
    };

    T query(int p, int l, int r, int i, int j){
        propagate(p, l, r);
        if (l >= i && r <= j){
            return st_[p];
        }
        int mid = (l + r) >> 1;
        if (j <= mid) {
            return query(p << 1, l, mid, i, j);
        }
        else if (i > mid) {
            return query(p << 1 | 1, mid + 1, r, i, j);
        }
        else {
            return (query(p << 1, l, mid, i, mid) + query(p << 1 | 1, mid + 1, r, mid + 1, j));
        }
    }

    void build(const vector<T>& s, int p, int l, int r){
        if (l == r){
            st_[p] = s[l];
        }
        else{
            int mid = (l + r) >> 1;
            build(s, p << 1, l, mid);
            build(s, p << 1 | 1, mid + 1, r);
            st_[p] = st_[p << 1] + st_[p << 1 | 1];
        }
    }

    void propagate(int p, int l, int r){
        if (lazy_[p] != flag_){
            st_[p].applyLazy(lazy_[p], r - l + 1);
            if (l != r){
                lazy_[p << 1] |= lazy_[p];
                lazy_[p << 1 | 1] |= lazy_[p];
            }
            lazy_[p] = flag_;
        }
    }
};


void solve(){
    int n, q;
    cin >> n >> q;

    vector<Node> a(n + 1);
    for (int i = 1; i <= n; ++i){
        cin >> a[i].sum;
    }

    SegmentTree<Node> st(a);
    while (q --){
        int k, x, y;
        cin >> k >> x >> y;
        if (k & 1){
            long long t;
            cin >> t;
            st.update(x, y, lazyNode(t));
        }
        else{
            cout << st.query(x, y) << '\n';
        }
    }
}

可以考虑在线段树初始化时lazyNode也作为模板类进行设置,当使用C语言变量时,可能会增加通用性。

标签:Node,sz,洛谷,int,线段,long,lazyNode,p3372,sum
From: https://www.cnblogs.com/yxcblogs/p/18145343

相关文章

  • 洛谷题单指南-动态规划1-P1049 [NOIP2001 普及组] 装箱问题
    原题链接:https://www.luogu.com.cn/problem/P1049题意解读:装尽可能多的物品,使得总体积越大越好,即剩余空间最小,还是一个01背包问题,物品的体积就是其价值。解题思路:01背包模版题,物品体积、价值相同,直接采用一维dp。100分代码:#include<bits/stdc++.h>usingnamespacestd;co......
  • 「杂题乱刷」洛谷 P2398
    典题。发现问题可以变为枚举\(i\),求出两两数\(gcd\)为\(i\)的个数,但是这样还是\(O(n^2)\)的。然后可以将两边同时除以\(i\),原式变为暴力筛复杂度是\(O(n\log_2(n))\)的,加个前缀和时间复杂度为\(O(n)\)。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是......
  • 洛谷题单指南-动态规划1-P1115 最大子段和
    原题链接:https://www.luogu.com.cn/problem/P1115题意解读:计算最大字段和,典型dp问题。解题思路:设a[]表示所有整数,f[i]表示以第i个数结束的最大字段和当f[i-1]>=0时,f[i]=f[i-1]+a[i]否则,f[i]=a[i]因此,递归式为f[i]=max(a[i],f[i-1]+a[i])注意整数可能为负,ans初始......
  • 线段树优化建图学习笔记
    关于线段树优化建图对于存在一些单点连向区间或区间连向单点的边,且直接暴力连边会爆炸的题目,就可以考虑使用线段树优化建图。边数量的规模将会是\(n\logn+a\)。例题题目链接。从\(s\)到\(t\)的最短路就是模板。如果暴力建边,最坏情况下需要建的边在\(n^2\)级别,显然是......
  • 洛谷题单指南-动态规划1-P1434 [SHOI2002] 滑雪
    原题链接:https://www.luogu.com.cn/problem/P1434题意解读:计算能滑行的最长距离。解题思路:设dp(i,j)表示从i,j可以滑行的最大距离对于4个方向i,j可以到达的点,ni,nj,如果可以滑过去(ni,ni所在点高度更低)则dp(i,j)=max(dp(i,j),1+dp(ni,nj))为了便于搜索4个方向的各条路径,......
  • 洛谷题单指南-动态规划1-P2196 [NOIP1996 提高组] 挖地雷
    原题链接:https://www.luogu.com.cn/problem/P2196题意解读:求一条路径,使得所有点地雷数之和最大。解题思路:1、DFS先建图,再从1~n点分别进行一次DFS,记录过程中地雷总数最大的,并且同时记录遍历的顺序。数据量不大,直接就可以过。100分代码:#include<bits/stdc++.h>usingnamespa......
  • [题解][洛谷P1174] 打砖块
    题目分析n行m列的砖块,起始有k发子弹。每次可以用一发子弹,打碎某一列当前处于这一列最下面的那块砖,并且得到相应的得分。某些砖块打碎以后会获得一个砖块。求最大得分。题解可以看出是一道动态规划题。关键在于如何设计状态。先考虑砖块打碎不会得到子弹的情况:这个时候可以......
  • LibreOJ-3038 「JOISC 2019 Day3」穿越时空 Bitaro <线段树> 题解
    审题一条链每条边有通行时间上下界限制通过一条边需要\(1\)单位时间站在当前节点时间减少\(1\)耗费\(1\)单位代价\(q\)次询问要么更改一条边的通信时间上下界要么询问在\(b\)时刻在城市\(a\),\(d\)时刻到达城市\(c\)的最小代价思想做题准备......
  • 洛谷题单指南-动态规划1-P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles
    原题链接:https://www.luogu.com.cn/problem/P1216题意解读:计算数字三角形最高点到最后一行路径之和最大值,典型线性DP。解题思路:设a[i][j]表示数字三角形的值,设dp[i][j]表示从最高点到第i行第j列路径之和的最大值,由于每一步可以走到左下方的点也可以到达右下方的点,所以dp[i][......
  • [题解][洛谷P1136] 迎接仪式
    题目描述对于一个由字母“j”和“z”组成的字符串,可以任意交换两个字符的位置不超过k次,求最多能出现多少个“jz”字串。题解动态规划题。设f[i][j][k][0/1]表示到第i位,前面交换了j个“j”,交换了k个“z”,且第i位是j(用0表示)或z(用1表示)。当j=k时即为可行解。为什么需要用第四维......