线段树lazy模板 luogu3372

线段树写得很少,这么基本的算法还是要会的……

#include<bits/stdc++.h>
using namespace std;
inline long long read() {
    long long x = 0, f = 1; char ch = getchar();
    while (ch<‘0‘ || ch>‘9‘) { if (ch == ‘-‘) f = -1;ch = getchar(); }
    while (ch >= ‘0‘&&ch <= ‘9‘) { x = x * 10 + ch - ‘0‘;ch = getchar(); }
    return x*f;
}
const int maxn = 131071;
int n,m,op,_l,_r,k;
struct NODE{
    int l,r;
    long long lazy,val;
}node[maxn<<2];
void pushup(int rt){
    node[rt].val = node[rt<<1].val+node[rt<<1|1].val;
}
void pushdown(int rt){
    if(!node[rt].lazy) return ;
    int mid = node[rt].l+node[rt].r >>1;
    node[rt<<1].lazy += node[rt].lazy;
    node[rt<<1|1].lazy += node[rt].lazy;
    node[rt<<1].val += node[rt].lazy*(mid-node[rt].l+1);
    node[rt<<1|1].val += node[rt].lazy*(node[rt].r-mid);
    node[rt].lazy = 0;

}
void build(int x,int l,int r){
    if((node[x].l = l) == (node[x].r = r)) return;
    int mid = node[x].l+node[x].r>>1;
    build(x<<1,l,mid),build(x<<1|1,mid+1,r);
}
//单点更新
void add_one(int rt,int pos,long long val){
    if(node[rt].l == node[rt].r){
        node[rt].val+=val;
        return;
    }
    int mid = node[rt].l+node[rt].r>>1;
    add_one(rt<<1|pos>mid,pos,val);
    pushup(rt);
}
//区域更新
//所谓lazy就是只有当需要pushdown时才pushdown,query同
void add(int rt,int l,int r,int val){
    pushdown(rt); // 这一行的作用见 https://jecvay.com/2014/11/segment-tree-lazy-design.html
    if(node[rt].l>=l && node[rt].r<=r){
        node[rt].val+=val*(node[rt].r-node[rt].l+1);
        node[rt].lazy += val;
        return ;
    }
    int mid = node[rt].l+node[rt].r>>1;
    if(l<=mid) add(rt<<1,l,r,val);
    if(r>mid) add(rt<<1|1,l,r,val);
    pushup(rt);
}
long long query(int rt,int l,int r){
    pushdown(rt);
    if(node[rt].l>=l && node[rt].r<=r) return node[rt].val;
    int mid = node[rt].l + node[rt].r >> 1;
    long long ans = 0;
    if(l<=mid) ans+=query(rt<<1,l,r); // 易错
    if(r>mid) ans+=query(rt<<1|1,l,r);
    return ans;
}
int main(){
    n = read(), m = read();
    build(1,0,n);
    for(int i = 0;i<n;i++) add_one(1,i,read());
    for(int i = 0;i<m;i++){
        op = read();_l = read()-1; _r = read()-1;
        if(op-1) printf("%lld\n",query(1,_l,_r));
        else{
            k = read();
            add(1,_l,_r,k);
        }
    }
    return 0;
}
时间: 09-02

线段树lazy模板 luogu3372的相关文章

线段树lazy标记??Hdu4902

Nice boat Time Limit: 30000/15000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 335    Accepted Submission(s): 159 Problem Description There is an old country and the king fell in love with a devil. The devil al

fzu 2171 线段树 lazy标记

http://acm.fzu.edu.cn/problem.php?pid=2171      Problem 2171 防守阵地 II Accept: 73    Submit: 256Time Limit: 3000 mSec    Memory Limit : 32768 KB Problem Description 部队中总共有N个士兵,每个士兵有各自的能力指数Xi,在一次演练中,指挥部确定了M个需要防守的地点,指挥部将选择M个士兵依次进入指定地点进行防守任务,获得的参考指数即为M个士兵

HDU4902:Nice boat(线段树lazy)

Problem Description There is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king used to be wise and beloved by his people. Now he is just like a boy in love and can't refus

FZU1608 Huge Mission 线段树lazy区间更新+求和

就这破题目坑了我一个大晚上,直到今天一觉醒过来才搞定,原因之一:这题目的题意真的是太狗了,还不如直接看着案例猜来的快啊, 题意:给了你一些区间,x,y,第三个参数w是效率,代表这段时间他的单位时间效率,效率总和就是 (y-x)*w,然后有的时间段会被重复啊,比如前面给了1,4,1,后面又给了2,4,3他们为了是的时间段1,4的效率总和最大肯定是选择  2,4区间的效率值选择3,意思就是后面出现更好的情况就覆盖前面的,问你总得最大效率和 当然这题目坑的原因还有一个就是以前学习线段树 做的时候都是看

POJ 3468 线段树+lazy标记

lazy标记 Time Limit:5000MS     Memory Limit:131072KB     64bit IO Format:%I64d & %I64u Submit Status Description You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to

HDU4893:Wow! Such Sequence!(线段树lazy)

Problem Description Recently, Doge got a funny birthday present from his new friend, Protein Tiger from St. Beeze College. No, not cactuses. It's a mysterious blackbox. After some research, Doge found that the box is maintaining a sequence an of n nu

[hiho 22]线段树-lazy标记的下放

题目描述 之前提到过,线段树之所以更新查询快,是因为区间更新有lazy标记使得不需要每次都操作到叶子节点. 但是如果要操作一个节点时,其父节点上的lazy标记应当被释放,否则该节点无法得到最新的正确结果. 因而lazy标记下放的策略是在需要操作某个节点的子节点时,将该节点的lazy标记全部下放.见第69行. 同时应当注意,给某个节点增加lazy标记时,不要忘了修改该节点的相关统计值.因为更新完该节点后还要马上修改其父节点的统计值.见第80行. 代码如下: #include <stdio.h>

Codeforces 242E. XOR on Segment (二维线段树 lazy操作 xor)

题目链接: http://codeforces.com/problemset/problem/242/E 题意: 给出一个序列,有两种操作,一种是计算l到r的和,另一种是让l到r的数全部和x做异或运算. 思路: from: http://blog.csdn.net/u013912596/article/details/39006317 很显然直接暴力是不可能的,又是两种操作,又想到了线段树..但是这并不简单,异或操作该怎么处理? 异或是一种位运算,如果x的第j位是1,那么说明l到r的每个数的第j

poj 4047 Garden 线段树lazy标记与成段更新

题意: 给长度为n的序列及k(0<k<=n<=200000),m个操作p,x,y.其中(1)p==0:将x位置处的数变为y;(2)p==1:将x,y位置处的数互换.(3)p==2查询x-y位置之间连续k个数的和的最大值. 分析: 求连续区间的和最大,可以把区间看成一个点,这样这n-k+1个区间的最大和可以看做n-k+1个点的最大值,当更新原序列中位置x的值就相当于更新区间中x-k+1到x区间的值,然后用线段树做成段更新.成段更新要用到lazy标记,我的理解是:当更新或query的时候如果