题解
- 线段树维护c[i]=b[i]-a[i]%b[i]的最小值以及$ans=\frac{a[i]}{b[i]}$(向下取整)的区间和,当有小于等于0的东西出现的时候就暴力往下更新
- 有的人可能会说这东西会T 0.0,是的如果没有题目上那句b is a static permutation of 1 to n.这个算法确实会T.既然b是1-n的一个排列,并且a[i]从0最多到m,所以总的是$\sum_{i=0}^n{\frac{m}{i}}$,这东西是个调和级数约等于$mlog(n)$,加个线段树显然复杂度是$O(m*{log^2(n)})$
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using namespace std;
const int N=1e5+7;
int nm[N],tr[N<<2],lz[N<<2],n,m;
ll ans[N<<2];
char op[10];
void pushdown(int o,int l,int r){
int v=lz[o];
lz[o<<1]+=v;
lz[o<<1|1]+=v;
tr[o<<1]-=v;
tr[o<<1|1]-=v;
lz[o]=0;
}
inline void pushup(int o,int l,int r){
tr[o]=min(tr[o<<1],tr[o<<1|1]);
ans[o]=ans[o<<1]+ans[o<<1|1];
}
void build(int o,int l,int r){
lz[o]=0;
if(l==r){
scanf("%d",&nm[l]);
tr[o]=nm[l];
ans[o]=0;
return ;
}
int mid=l+r>>1;
build(lson);
build(rson);
pushup(o,l,r);
}
void update(int o,int l,int r,int L,int R){
if(L<=l&&R>=r){
tr[o]--;
if(tr[o]>0){lz[o]++;return ;}
if(l==r&&tr[o]<=0){
tr[o]+=nm[l];
ans[o]++;
return ;
}
}
if(lz[o])pushdown(o,l,r);
int mid=l+r>>1;
if(L<=mid)update(lson,L,R);
if(R>mid)update(rson,L,R);
pushup(o,l,r);
}
ll query(int o,int l,int r,int L,int R){
if(L<=l&&R>=r)return ans[o];
if(lz[o])pushdown(o,l,r);
int mid=l+r>>1;
ll res=0;
if(L<=mid)res+=query(lson,L,R);
if(R>mid)res+=query(rson,L,R);
return res;
}
int main(){
while(~scanf("%d%d",&n,&m)){
build(1,1,n);
while(m--){
int l,r;
scanf("%s%d%d",op,&l,&r);
if(op[0]=='a')update(1,1,n,l,r);
else printf("%lld\n",query(1,1,n,l,r));
}
}
return 0;
}