题解：http://www.cnblogs.com/zyfzyf/p/4105184.html

一、下传标记写法

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 #define lson rt<<1,l,m 6 #define rson rt<<1|1,m+1,r 7 int Num,CH[12],f,c; 8 inline void R(int &x){ 9     c=0;f=1;10     for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;11     for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');12     x*=f;13 }14 typedef long long ll;15 int n,m,w[1000001],now[1000001],b[1000001],fa[1000001];16 ll ans,maxv[4000001],delta[4000001];17 void pushdown(int rt)18 {19     if(delta[rt])20       {21         delta[rt<<1]+=delta[rt]; delta[rt<<1|1]+=delta[rt];22         maxv[rt<<1]+=delta[rt]; maxv[rt<<1|1]+=delta[rt];23         delta[rt]=0;24       }25 }26 void update(int ql,int qr,int v,int rt,int l,int r)27 {28     if(ql<=l&&r<=qr)29       {30         delta[rt]+=(ll)v;31         maxv[rt]+=(ll)v;32         return;33       }34     pushdown(rt); int m=l+r>>1;35     if(ql<=m) update(ql,qr,v,lson);36     if(m
        
         >1; ll res=0;44     if(1<=m) res=max(res,query(qr,lson));45     if(m
        
       
      
     

二、不下传标记写法

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 #define lson rt<<1,l,m 6 #define rson rt<<1|1,m+1,r 7 int Num,CH[12],f,c; 8 inline void R(int &x){ 9     c=0;f=1;10     for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;11     for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');12     x*=f;13 }14 typedef long long ll;15 int n,m,w[1000001],now[1000001],b[1000001],fa[1000001];16 ll ans,maxv[4000001],delta[4000001];17 void update(int ql,int qr,int v,int rt,int l,int r)18 {19     if(ql<=l&&r<=qr)20       {21         delta[rt]+=(ll)v;22         return;23       }24     int m=l+r>>1;25     if(ql<=m) update(ql,qr,v,lson);26     if(m
        
         >1; ll res=0;33     if(1<=m) res=max(res,query(qr,lson));34     if(m