题意：
思路：
考虑a[i]对答案的贡献，当a[i]加上b[i]个1时，贡献+1，可以令a[i]=b[i]，每次操作答案减1，维护区间最小值。
区间减的时候不需要维护“区间和减”，而是直接区间最小值减1，更新tag，每次减1不会影响区间最小值，如果最小值为0，
找到a[i]等于0的结点，答案+1即可，如果区间最小值>1，就只需要修改这个区间，打个标记。可以发现，普通区间修改操作是log(n)的，
考虑最坏情况，即每次的l=1,r=n，所有点对答案的贡献为：T+T/2+T/3+....+T/T=Tlog(T)，为调和级数，所以总的时间复杂度为：T*log(T)*log(n)，log(n)为深度。
实际上不需要考虑，如果每次只修改最小值那么其它结点会不会修改，因为我们打了tag，在需要的时候会下传到叶子结点，此时的Min[i]=a[i]。
为什么不暴力？
如果暴力区间修改，每次会修改n个点，深度为log(n),操作数为T，时间复杂度为T*n*log(n)。
可以发现，记录tag就把o(n)优化为o(log(T))，因为我们只需要更改有贡献的叶子结点，没有贡献的在父节点就回溯了。
代码：//代码与题目有差别。
#include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<queue> #include<cstring> #define R register #define ll long long int using namespace std; const int N=4e5+100; int n,m,b[N],tag[N],Sum[N],Min[N]; void build(int l,int r,int p){ if(l==r){ Sum[p]=0; Min[p]=b[l]; return; } R int mid=(l+r)>>1; build(l,mid,p<<1); build(mid+1,r,p<<1|1);//ｓｕｍ存答案 Min[p]=min(Min[p<<1],Min[p<<1|1]); } void f(int l,int r,int k,int p){ Min[p]+=k; tag[p]+=k; } inline void pushdown(R int l,R int r,R int p){ R int mid=(l+r)>>1; f(l,mid,tag[p],p<<1); f(mid+1,r,tag[p],p<<1|1); tag[p]=0; } void update(int l,int r,int x,int y,int k,int p){ if((l>=x&&r<=y)&&Min[p]>1){ Min[p]+=k;//更新最小值 tag[p]+=k;//下传更新 return; } if((Min[p]==1)&&(l==r)){ tag[p]=0; Sum[p]++; Min[p]=b[l]; return; } pushdown(l,r,p); R int mid=(l+r)>>1; if(x<=mid)update(l,mid,x,y,k,p<<1); if(y>mid)update(mid+1,r,x,y,k,p<<1|1); Min[p]=min(Min[p<<1],Min[p<<1|1]); Sum[p]=Sum[p<<1]+Sum[p<<1|1]; } int ask(int l,int r,int x,int y,int p){ int tot=0; if(l>=x&&r<=y)return Sum[p]; pushdown(l,r,p); int mid=(l+r)>>1; if(x<=mid)tot+=ask(l,mid,x,y,p<<1); if(y>mid)tot+=ask(mid+1,r,x,y,p<<1|1); return tot; } int main(){ scanf("%d%d",&n,&m); for(R int i=1;i<=n;i++) scanf("%d",&b[i]); build(1,n,1); for(R int i=1;i<=m;i++){ int opt,l,r; scanf("%d%d%d",&opt,&l,&r); if(opt==1) update(1,n,l,r,-1,1); else printf("%d ",ask(1,n,l,r,1)); } return 0; }