<题目链接>
题目大意：
给出两个序列，a序列全部初始化为0，b序列为输入值。然后有两种操作，add x y就是把a数组[x,y]区间内全部+1，query x y是查询[x,y]区间内∑[ai/bi]。([ai/bi]代表ai/bi后向下取整)
解题分析：
首先，如果每次+1都暴力更新到每个叶子节点肯定会超时，但是如果不更新到叶子节点又不好维护每个节点对应区间 ∑[ai/bi] 的值，所以我们可以每个节点都维护四个值。sum值代表这个区间每个节点整数部分的所有数之和，lazy进行懒惰标记，避免每次更新到叶子节点，mxa记录该区间内分子的最大值，mnb记录该区间内分母的最小值。之所以要维护这两个最大最小值是因为，当进行区间整体+1操作的时候，如果该区间内最大的分子都小于分母时，说明这个区间在进行+1操作后，并没有对该区间的sum值做出贡献，所以此时就可以将这个+1操作lazy到这个节点；但是如果对区间整体+1后，最大分子大于等于最小分母，此时，就需要继续向下更新，直到找到那个(或者几个)分子大于等于分母的根节点，然后将该节点的sum+1，同时将b值加上原始的brr[l]值（其实我不太明白这一步为什么要这么做，我觉的这步等效于该点的mxa值-该点的mnb值啊，然而这样改了以后超时 T_T）。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define Lson rt<<1,l,mid
#define Rson rt<<1|1,mid+1,r
const int M =1e5+; int n,m;
struct Tree{
int lazy,sum;
int mxa,mnb;
}tr[M<<];
int brr[M]; void Pushdown(int rt){
if(tr[rt].lazy){
int tmp=tr[rt].lazy;
tr[rt<<].lazy+=tmp,tr[rt<<|].lazy+=tmp;
tr[rt<<].mxa+=tmp,tr[rt<<|].mxa+=tmp;
tr[rt].lazy=;
}
}
void Pushup(int rt){
tr[rt].sum=tr[rt<<].sum+tr[rt<<|].sum;
tr[rt].mxa=max(tr[rt<<].mxa,tr[rt<<|].mxa); //维护该区间内分子的最大值和分母的最小值
tr[rt].mnb=min(tr[rt<<].mnb,tr[rt<<|].mnb);
}
void build(int rt,int l,int r){ //初始化
tr[rt].lazy=;
if(l==r){
tr[rt].mxa=tr[rt].sum=;
tr[rt].mnb=brr[l];
return;
}
int mid=(l+r)>>;
build(Lson);
build(Rson);
Pushup(rt);
}
void update(int rt,int l,int r,int L,int R){ //这个函数是本题的关键
if(L<=l&&r<=R){
tr[rt].mxa++;
if(tr[rt].mxa<tr[rt].mnb){ //如果最大的分子小于最大的分母，说明这个区间内的所有叶子在分子+1之后，没有对sum值多做出贡献，所以我们先将这个操作lazy在这个节点
tr[rt].lazy++;
return;
}
if(l==r&&tr[rt].mxa>=tr[rt].mnb){ //如果向下找到了那个分子大于等于分母的叶子节点，那么该节点贡献+1，且将分母加上最初始的防御值，相当于将该真分数的整数部分提出后，再将其变成假分数，方便以后继续统计贡献
tr[rt].sum++;
tr[rt].mnb+=brr[l]; //我觉的这一步应该等效于tr[rt].mxa-=tr[rt].mnb啊，然而这样改了以后超时
return;
}
}
Pushdown(rt);
int mid=(l+r)>>;
if(L<=mid)update(Lson,L,R);
if(R>mid)update(Rson,L,R);
Pushup(rt);
}
int query(int rt,int l,int r,int L,int R){ //查询该区间内所有数的整数部分之和
if(L<=l&&r<=R)return tr[rt].sum;
Pushdown(rt);
int ans=;
int mid=(l+r)>>;
if(L<=mid)ans+=query(Lson,L,R);
if(R>mid)ans+=query(Rson,L,R);
return ans;
}
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=;i<=n;i++)
scanf("%d",&brr[i]);
build(,,n);
char op[];
while(m--){
int x,y;
scanf("%s%d%d",&op,&x,&y);
if(op[]=='a')update(,,n,x,y);
else printf("%d\n",query(,,n,x,y));
}
}
return ;
}
2018-10-15