题目概述

给出排列 $\{b_n\}$ 和刚开始都是 $0$ 的 $\{a_n\}$ ，有两种操作：1.把 $a_{[L,R]}$ 都 $+1$ 。2.询问 $\sum_{i=L}^{R}\lfloor{a_i\over b_i}\rfloor$ 。

解题报告

除法……排列……调和级数？如果我们认为 $a_i$ 每 $b_i$ 次提供 $1$ 的贡献，那么总贡献最多为 $\sum_{i=1}^{n}\lfloor{q\over i}\rfloor$ 。

所以总贡献不会很多，我们可以直接暴力做，唯一的问题就是如何在修改后快速找到提供贡献的点。

线段树大法好，区间减区间查询最小值就行了。

ps：怎么我只会数据结构题啊。

示例程序

清 $tag$ 的时候清在了 $L==R$ 里面，我tm……

1
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
#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef pair<int,int> data;
const int maxn=100000;

int n,te,b[maxn+5],c[maxn+5];
int ID[(maxn<<2)+5],MIN[(maxn<<2)+5],tag[(maxn<<2)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline void Update(int x,int tem) {for (int i=x;i<=n;i+=i&-i) c[i]+=tem;}
inline int Sum(int x) {int sum=0;for (int i=x;i;i-=i&-i) sum+=c[i];return sum;}
inline void Pushup(int p){
    if (MIN[p<<1]<MIN[p<<1|1]) MIN[p]=MIN[p<<1],ID[p]=ID[p<<1];
    else MIN[p]=MIN[p<<1|1],ID[p]=ID[p<<1|1];
}
void Build(int L,int R,int p=1){
    tag[p]=0;if (L==R) {ID[p]=L;MIN[p]=b[L];return;}int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p);
}
inline void Pushdown(int p){
    int now=tag[p];tag[p]=0;if (!now) return;
    MIN[p<<1]+=now;tag[p<<1]+=now;MIN[p<<1|1]+=now;tag[p<<1|1]+=now;
}
void Insert(int L,int R,int k,int l=1,int r=n,int p=1){
    if (R<l||r<L) return;if (L<=l&&r<=R) {MIN[p]+=k;tag[p]+=k;return;}int mid=l+(r-l>>1);
    Pushdown(p);Insert(L,R,k,l,mid,p<<1);Insert(L,R,k,mid+1,r,p<<1|1);Pushup(p);
}
data Min(int L,int R,int l=1,int r=n,int p=1){
    if (R<l||r<L) return mp(2e9,0);if (L<=l&&r<=R) return mp(MIN[p],ID[p]);int mid=l+(r-l>>1);
    Pushdown(p);return min(Min(L,R,l,mid,p<<1),Min(L,R,mid+1,r,p<<1|1));
}
inline void Add(int L,int R){
    Insert(L,R,-1);data now=Min(L,R);
    while (!now.fr){
        Insert(now.sc,now.sc,b[now.sc]);
        Update(now.sc,1);now=Min(L,R);
    }
}
inline int Ask(int L,int R) {return Sum(R)-Sum(L-1);}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    while (~readi(n)){
        readi(te);for (int i=1;i<=n;i++) readi(b[i]),c[i]=0;
        for (Build(1,n);te;te--){
            char ch=readc();while (!islower(ch)) ch=readc();
            int L,R;readi(L);readi(R);
            if (ch=='a') Add(L,R); else printf("%d\n",Ask(L,R));
        }
    }
    return 0;
}