题意

我们定义一个数字 $d$ 的权值为可以进行以下操作的次数。

• 对于所有的 $a_i \gets a_i - d$。如果操作之后有新的数字小于等于 $0$，那么再进行一次操作。

现在有 $m$ 次操作，要支持加入一个数字，区间 $[l,r]$ 所有数字的权值和。

分析

首先对一个数字 $d$ 来说，我们只要考虑区间 $(0,d],(d,2d],(2d,3d]\dots(kd,(k+1)d]$ 区间内是否有数字。我们用 $(d,k)$ 表示区间 $(kd,(k+1)d]$。这样子，一个数字最多有 $\left \lceil \frac{n}{d} \right \rceil$ 个区间，而区间总个数就是调和级数 $O(n\log n)$

可以把 $[l,r]$ 拆成 $[1,r]-[1,l-1]$ 两个区间，我们就只要处理前缀的和即可。但是直接做是难的，我们考虑转化，从每个数字入手。对于 $(d,k)$ 来说，如果 $(d,1 \sim k)$ 都有数字了，那么 $(d,k)$ 就会对后面所有的 $d$ 产生 $1$ 的贡献。我们可以处理出来 $(d,k)$ 什么时候产生贡献。

我们设 $t_{d,k}$ 表示 $(d,k)$ 什么时候第一次有数字。这个是好做的，直接 ST 表乱搞一下就行。然后是处理 $(d,k)$ 什么时候有贡献。其实就是之前所有区间都有数字的时候，也就是 $\max_{i=0}^k t(d,i)$。然后我们就知道了什么时候有贡献，用 vector 存一下，然后按照时间轴再跑一次，用树状数组维护单点加，区间查询。

代码实现的时候，我们不用真的开出来 $t$ 数组，可以直接用 ST 表的查询代替。

时间复杂度因为有 $O(n\log n)$ 个区间，每个区间要一次树状数组，所以是 $O(n\log^n)$ 的。然后每个询问要查询一次，所以是 $O(m\log n)$ 的。总的时间复杂度就是 $O(n\log^2n+m\log n)$。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define N 100005
#define M 1000005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, m, a[N], op, l, r, x, ql[M], qr[M];
vector <int> upd[M];

struct ST_table{
    int f[N][25], lg[N];
    il void init(){
        for (int i = 1; i <= n; i++) f[i][0] = a[i];
        for (int j = 1; j <= 20; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    }
    il int mink(int l, int r){
        int p = lg[r - l + 1];
        return min(f[l][p], f[r - (1 << p) + 1][p]);
    }
}ST;
struct BIT{
    int tr[N];
    il void add(int x, int k){for (int i = x; i <= n; i += (i & (-i))) tr[i] += k;}
    il int ask(int x){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans += tr[i];return ans;}
}B;
int main(){
    n = rd(), m = rd();
    for (int i = 1; i <= n; i++) a[i] = m + 1;
    for (int i = 1; i <= m; i++){
        op = rd();
        if (op == 1) ql[i] = qr[i] = -1, x = rd(), a[x] = min(a[x], i);
        else ql[i] = l = rd(), qr[i] = r = rd();
    }
    ST.init();
    for (int i = 1; i <= n; i++){
        B.add(i, 1);
        int maxn = 0;
        for (int j = 1; j <= n; j += i) maxn = max(maxn, ST.mink(j, min(j + i - 1, n))), upd[maxn].push_back(i);
    }
    for (int i = 1; i <= m; i++){
        for (auto x : upd[i]) B.add(x, 1);
        if (~ql[i]) printf ("%d\n", B.ask(qr[i]) - B.ask(ql[i] - 1));
    }
    return 0;
}