题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6315
题目大意：告诉你a,b两个数组，a数组初始化为0，b数组告诉你长度和具体值，接下来有q次操作，add操作是从向区间[l,r]加1，query操作是求区[l,r]的ai/bi的总和。
解题思路：维护一个mn,表示这个区间里的a最少加几次才能有新的贡献。比如1最多对总和造成q的贡献，2最多q/2，q/3，q/4,一直到q/n。最少要加min(b[i]-a[i]%b[i]）次才能有新的贡献，如果这个区间+1之后没有贡献,也就是mn>1,就直接打标记.
AC代码：
#include<iostream>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
#define lson rt<<1
#define rson rt<<1|1
#define Lson l,m,lson
#define Rson m+1,r,rson
typedef long long ll; const ll mod= 1e9+;
const int maxn=1e5+; int n;
int a[maxn],b[maxn];
char s[]; int lazy[maxn<<],sum[maxn<<],mn[maxn<<];
void pushup(int rt){
sum[rt]=sum[lson]+sum[rson];
mn[rt]=min(mn[lson],mn[rson]);
}
void pushdown(int rt,int m){
if(lazy[rt]==){
return;
}
lazy[lson]+=lazy[rt];
lazy[rson]+=lazy[rt];
mn[lson]-=lazy[rt];
mn[rson]-=lazy[rt];
lazy[rt]=;
} void build(int l,int r,int rt){
lazy[rt]=;
sum[rt]=;
if(l==r){
mn[rt]=b[l];
return ;
}
int m=(l+r)>>;
build(Lson);
build(Rson);
pushup(rt);
} void update(int L,int R,int add,int l,int r,int rt){
if(L<=l&&r<=R&&mn[rt]>){
lazy[rt]++,mn[rt]--;
return ;
}
if(l==r){
sum[rt]++;
mn[rt]=b[l];
return ;
}
pushdown(rt,r-l+);
int m=(l+r)>>;
if(L<=m) update(L,R,add,Lson);
if(m<R) update(L,R,add,Rson);
pushup(rt);
} int query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return sum[rt];
}
pushdown(rt,r-l+);
int m=(r+l)>>,ret=;
if(L<=m) ret+=query(L,R,Lson);
if(m<R) ret+=query(L,R,Rson);
return ret;
}
int main(){
int q;
while(~scanf("%d%d",&n,&q)){
for(int i=;i<=n;i++){
scanf("%d",&b[i]);
}
build(,n,);
while(q--){
int l,r;
scanf("%s %d %d",s,&l,&r);
if(s[]=='a'){
update(l,r,,,n,);
}else{
printf("%d\n",query(l,r,,n,));
}
}
}
return ;
}