HDU 6315 Naive Operations(线段树+懒惰标记)

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6315

题意：一行给出n,m，有两个数组，长度为n,其中a数组全为0，b数组接下来一行给你n个数

接着m行是m条命令：

add l r               a数组[l,r]区间的数全都加一

query l r              [l,r] 区间的数  求和，      每个数为a[i]/b[i]

一开始用树状数组做的，TLE了，比赛结束用线段数做的，不懒惰标记依然会TLE

考虑到区间每次加一后，如果求和值不一定会加一，只有当a[i]加了一个b[i]才会加1；

这样每次当a[i]加到一个b[i]时结果加一，用cnt表示结果，laz是加的数，然后cnt++后要让b[i]加上原来的一个b[i]

例如   1 5 2 4 3

对最后一个b[5]而言，a[5]要加3次值才会加一，那么加一之后让b[5]加上原来的一个b[5]变成6，依旧是让a[5]加3次结果加一

#include <bits/stdc++.h> #define N 100005 #define lc (d<<1) #define rc (d<<1|1) #define m (l+r>>1) using namespace std; struct NODE{     int laz,cnt,min,max; }; int b[N]; NODE node[4*N]; int n; void pushUp(int d) {     node[d].min=min(node[lc].min,node[rc].min);     node[d].max=max(node[lc].max,node[rc].max);     node[d].cnt=node[lc].cnt+node[rc].cnt; } void pushDown(int d) {     if(node[d].laz)     {         int v=node[d].laz;         node[d].laz=0;          node[lc].laz+=v;         node[rc].laz+=v;         node[lc].max+=v;         node[rc].max+=v;//由于每次是让b[i]加上自身并不是清零，所以这里也是加v      }  } void build(int l,int r,int d) {     node[d].laz=0;     if(l==r)     {         node[d].cnt=node[d].max=0;         node[d].min=b[l];         return;     }     build(l,m,lc);     build(m+1,r,rc);     pushUp(d); } void updata(int l,int r,int L,int R,int d) {     if(L<=l&&r<=R)     {         node[d].max++;         if(node[d].max<node[d].min)         {             node[d].laz++;             return;         }          if(l==r&&node[d].max>=node[d].min)         {             node[d].cnt++;//结果加一             node[d].min+=b[l];              return;         }     }      pushDown(d);     if(L<=m)         updata(l,m,L,R,lc);     if(R>m)         updata(m+1,r,L,R,rc);     pushUp(d); }

int query(int l,int r,int L,int R,int d) {     if(L<=l&&r<=R)     {         return node[d].cnt;     }     pushDown(d);     int ans=0;     if(L<=m)     ans+=query(l,m,L,R,lc);     if(R>m)     ans+=query(m+1,r,L,R,rc);      return ans; } int main() {     int q;     int x,y;     while(~scanf("%d %d",&n,&q))     {         for(int i=1; i<=n; i++)         {             scanf("%d",&b[i]);         }         build(1,n,1);         char op[6];         int l,r;         while(q--)         {             scanf("%s%d%d",op,&l,&r);             if(op[0]=='a')             {                 updata(1,n,l,r,1);             }             else             {                 printf("%d\n",query(1,n,l,r,1));             }         }     }     return 0; }