poj 3468 A Simple Problem with Integers 模板题线段树懒惰标记-白红宇

poj 3468 A Simple Problem with Integers 模板题线段树懒惰标记

阅读量：4113 次

发布时间：2019-05-25

本文共 1532 字，大约阅读时间需要 5 分钟。

题意：给你n个数字，进行操作1.求下标[l,r]区间的和（Q），2.将[l,r]区间的每个数+v(C)；

分析：线段树关键在与对于每个节点维护一个lazy值和一个sum值，lazy代表其维护的区间每个

节点都要加上的数，sum代表其下的数值之和，则以该节点k为根的子树维护的区间的和为

（r-l）*lazy[k]+sum[k]；

需要注意的是：当当前查询的区间与需要加数的区间完全重合时，则对该节点k进行懒惰标记

lazy[k]+=v，

否则，当前节点k的sum+=（该区间与需要加数区间的交集）*v;那么该节点的返回值

仍为其维护的区间之和，不过接下来要递归进入其左子树和右子树中进行懒惰标记。

核心思想是

保证每个节点的sum+lazy*(r-l)为维护其区间的和。

#include 
      
        #include
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int maxn=100000; ll data[4*maxn+5],datb[4*maxn+5],l[maxn+5],r[maxn+5],v[maxn+5]; char op[maxn+5][3]; ll max(ll a,ll b) { return a>b?a:b; } ll min(ll a ,ll b) { return a
                
                 a&&l
                 
                  >1,l,r); ll right=s(2*k+2,(a+b)>>1,b,l,r); sum=data[k]*(min(b,r)-max(a,l))+left+right; } return sum; } void add(int k,int a,int b,int l,int r,int v) { if(l<=a&&b<=r) data[k]+=v; else if(r>a&&l
                  
                   >1,l,r,v); add(2*k+2,(a+b)>>1,b,l,r,v); } } int main() { int n,c,temp; while(~scanf("%d %d",&n,&c)) { for(int i=1;i<=n;i++) { scanf("%d",&temp); add(0,1,n+1,i,i+1,temp); } for(int i=1;i<=c;i++) { scanf("%s",op[i]); if(op[i][0]=='Q') scanf("%d %d",&l[i],&r[i]); else scanf("%d %d %d",&l[i],&r[i],&v[i]); } for(int i=1;i<=c;i++) { if(op[i][0]=='Q') printf("%lld\n",s(0,1,n+1,l[i],r[i]+1)); else add(0,1,n+1,l[i],r[i]+1,v[i]); } } return 0; }