线段树(lazy标记)

  1 # include<cstdio>
  2 # include<iostream>
  3
  4 using namespace std;
  5
  6 # define MAX 100004
  7 # define lid id<<1
  8 # define rid id<<1|1
  9
 10 typedef long long LL;
 11 int n;
 12
 13 struct Segtree
 14 {
 15     int l,r;
 16     LL lazy,sum;
 17     inline int len()
 18     {
 19         return r-l+1;
 20     }
 21 }tree[MAX*4];
 22
 23 int a[MAX];
 24
 25 void push_up( int id )
 26 {
 27     tree[id].sum = tree[rid].sum+tree[lid].sum;
 28 }
 29
 30 void push_down( int id )
 31 {
 32     if ( tree[id].lazy==0 )
 33         return;
 34     tree[lid].lazy += tree[id].lazy;
 35     tree[rid].lazy += tree[id].lazy;
 36     tree[lid].sum += tree[id].lazy*tree[lid].len();
 37     tree[rid].sum += tree[id].lazy*tree[rid].len();
 38     tree[id].lazy = 0;
 39 }
 40
 41 void build( int id,int l,int r )
 42 {
 43     tree[id].l = l; tree[id].r = r;
 44     if ( l==r )
 45     {
 46         tree[id].sum = a[l];
 47         return;
 48     }
 49     int mid = (tree[id].l+tree[id].r)/2;
 50     build(lid,l,mid);
 51     build(rid,mid+1,r);
 52     push_up(id);
 53 }
 54
 55 void update( int id,int l,int r,int val )
 56 {
 57     if ( tree[id].l==l&&tree[id].r==r )
 58     {
 59         tree[id].lazy += val;
 60         tree[id].sum += 1LL*val*tree[id].len();
 61         return;
 62     }
 63     push_down(id);
 64     int mid = ( tree[id].l+tree[id].r )/2;
 65     if ( r <= mid )
 66         update(lid,l,r,val);
 67     else if ( l > mid )
 68         update(rid,l,r,val);
 69     else
 70     {
 71         update(lid,l,mid,val);
 72         update(rid,mid+1,r,val);
 73     }
 74     push_up(id);
 75 }
 76
 77 LL query( int id,int l,int r )
 78 {
 79     if ( tree[id].l==l&&tree[id].r==r )
 80     {
 81         return tree[id].sum;
 82     }
 83     push_down(id);
 84     int mid = ( tree[id].l+tree[id].r )/2;
 85     if ( r <= mid )
 86         return query(lid,l,r);
 87     else if ( l > mid )
 88         return query(rid,l,r);
 89     else
 90         return query(lid,l,mid)+query(rid,mid+1,r);
 91 }
 92
 93 int main(void)
 94 {
 95     while ( scanf("%d",&n)!=EOF )
 96     {
 97         for ( int i = 1;i <= n;i++ )
 98         {
 99             scanf("%d",&a[i]);
100         }
101         build(1,1,n);
102         int q; scanf("%d",&q);
103         while( q-- )
104         {
105             int ll,rr,t3; scanf("%d%d%d",&ll,&rr,&t3);
106             update(1,ll,rr,t3);
107             LL ans = query(1,ll,rr);
108             printf("%lld\n",ans);
109         }
110     }
111
112     return 0;
113 }
时间: 08-05

线段树(lazy标记)的相关文章

线段树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个士兵

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

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

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

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的时候如果

poj3468 线段树+lazy标记

A Simple Problem with Integers Time Limit: 5000MS   Memory Limit: 131072K Total Submissions: 92921   Accepted: 28910 Case Time Limit: 2000MS Description You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of

C++-POJ2777-Count Color[线段树][lazy标记][区间修改]

1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int MAXN=1e5+10; 5 struct node{int l,r,lazy,color;}t[MAXN*4]; 6 int L,R,C,n,m,q; 7 #define ls t[x].l 8 #define rs t[x].r 9 int count(int x){int ans=0;for(;x;x>>=1)

题解报告:hdu 1698 Just a Hook(线段树lazy标记的运用)

Problem Description In the game of DotA, Pudge's meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length.Now Pudge wants to do some operations on th

HDU 1698 Just a Hook (线段树延迟标记(lazy))

题意:有n个数初始值都为1,m个操作a,b,c,表示把区间[a,b]变为c,求最后n个数的和. 经典区间更新求和问题,需要用到延迟标记(或者说是懒惰标记),简单老说就是每次更新 的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新或询问的时候. #include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<map> #include<cm