让ci = ai / bi, 求sum(ci)的值，因为每次 ai 都是加一的，那么我可以用一颗线段树来维护每个 i 位置的 ai 距离达到 bi 还需要的数的最小值，更新是每次都减一，如果我某一个区间的最小值等于 0， 这就说明我这时候的ai已经满足了ai/bi==1的情况，那么对应的ci的位置就应该加一，所以我每次发现一个区间的最小值是0的话，我就 dfs 去找到为0的地方，把这里重新修改成bi，然后这个位置的答案+1就可以了
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define first fi
#define second se
#define lowbit(x) (x & (-x)) typedef unsigned long long int ull;
typedef long long int ll;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = ;
const int maxm = ;
const int mod = ;
using namespace std; int n, m, tol, T;
int a[maxn];
int b[maxn];
int c[maxn << ];
int sum[maxn << ];
int lazy[maxn << ]; void init() {
memset(a, , sizeof a);
memset(b, , sizeof b);
memset(c, , sizeof c);
memset(sum, inf, sizeof sum);
memset(lazy, , sizeof lazy);
} void pushup(int root) {
sum[root] = min(sum[root << ], sum[root << | ]);
c[root] = c[root << ] + c[root << | ];
} void pushdown(int root) {
if(lazy[root] != ) {
lazy[root << ] += lazy[root];
lazy[root << | ] += lazy[root];
sum[root << ] -= lazy[root];
sum[root << | ] -= lazy[root];
lazy[root] = ;
}
return ;
} void build(int left, int right, int root) {
if(left == right) {
sum[root] = b[left];
return ;
}
int mid = (left + right) >> ;
build(left, mid, root << );
build(mid+, right, root << | );
pushup(root);
} void dfs(int left, int right, int root) {
if(left == right) {
if(sum[root] == ) {
sum[root] = b[left];
c[root]++;
}
return ;
}
pushdown(root);
int mid = (left + right) >> ;
if(sum[root << ] == )
dfs(left, mid, root << );
if(sum[root << | ] == )
dfs(mid+, right, root << | );
pushup(root);
} void update(int left, int right, int prel, int prer, int root) {
if(prel <= left && right <= prer) {
lazy[root]++;
sum[root]--;
while(sum[root] == ) dfs(left, right, root);
return ;
}
pushdown(root);
int mid = (left + right) >> ;
if(prel <= mid) update(left, mid, prel, prer, root << );
if(prer > mid) update(mid+, right, prel, prer, root << | );
pushup(root);
} int query(int left, int right, int prel, int prer, int root) {
if(prel <= left && right <= prer) return c[root];
int mid = (left + right) >> ;
int ans = ;
if(prel <= mid) ans += query(left, mid, prel, prer, root << );
if(prer > mid) ans += query(mid+, right, prel, prer, root << | );
return ans;
} int main() {
while(~scanf("%d%d", &n, &m)) {
init();
for(int i=; i<=n; i++) scanf("%d", &b[i]);
build(, n, );
char str[];
while(m--) {
int l, r;
scanf("%s%d%d", str, &l, &r);
if(str[] == 'a') {
update(, n, l, r, );
} else if(str[] == 'q') {
int ans = query(, n, l, r, );
printf("%d\n", ans);
}
}
}
return ;
}