G - Naive Operations
一开始想到了线段树，但是没仔细思考如何操作。
大概就是维护区间最小值，如果最小值小于等于0才继续往下推。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int b[maxn];
struct node
{int mi,lazy,sum;node(int mi,int lazy,int sum):mi(mi),lazy(lazy),sum(sum) {}node() {}
} nodes[maxn<<2];
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
void build(int l,int r,int rt)
{nodes[rt].lazy=0;nodes[rt].sum=0;if(l==r){nodes[rt].mi=b[l];return;}int m=l+r>>1;build(ls);build(rs);nodes[rt].mi=min(nodes[rt<<1].mi,nodes[rt<<1|1].mi);
}void pushdown(int rt)
{if(nodes[rt].lazy){nodes[rt<<1].mi-=nodes[rt].lazy;nodes[rt<<1].lazy+=nodes[rt].lazy;nodes[rt<<1|1].mi-=nodes[rt].lazy;nodes[rt<<1|1].lazy+=nodes[rt].lazy;nodes[rt].lazy=0;}
}void update(int L,int R,bool ok,int l,int r,int rt)
{if(L<=l&&r<=R){if(ok){nodes[rt].mi--;nodes[rt].lazy++;ok=false;if(nodes[rt].mi>0)return;}if(nodes[rt].mi>0)return;if(l==r){if(nodes[rt].mi<=0){nodes[rt].sum++;nodes[rt].mi=((nodes[rt].mi)%b[l]+b[l])%b[l];if(nodes[rt].mi==0)nodes[rt].mi=b[l];}return;}}pushdown(rt);int m=l+r>>1;if(L<=m)update(L,R,ok,ls);if(R>m)update(L,R,ok,rs);nodes[rt].sum=nodes[rt<<1].sum+nodes[rt<<1|1].sum;nodes[rt].mi=min(nodes[rt<<1].mi,nodes[rt<<1|1].mi);
}
int query(int L,int R,int l,int r,int rt)
{if(L<=l&&r<=R)return nodes[rt].sum;int m=l+r>>1;int res=0;if(L<=m)res+=query(L,R,ls);if(R>m)res+=query(L,R,rs);return res;
}int main()
{int n,q;while(~scanf("%d %d",&n,&q)){for(int i=1; i<=n; i++)scanf("%d",&b[i]);build(1,n,1);char s[10];int l,r;while(q--){scanf("%s %d %d",s,&l,&r);if(s[0]=='a'){update(l,r,1,1,n,1);}else{printf("%d\n",query(l,r,1,n,1));}}}return 0;}