考虑线段树，显然操作 1,3,4 均能用线段树解决。

操作 2 并不好处理，如果直接硬除，操作复杂度为单次 $O(n)$。

考虑将其转化为便于线段树维护的操作。

对于区间 $[l,r]$，记 $p$ 为 $[l,r]$ 间的最大值，$q$ 为 $[l,r]$ 的最小值。

若 $p-\lfloor \frac{p}{d}\rfloor=q-\lfloor \frac{q}{d}\rfloor$，那么此时可以将这个操作转化为区间加法。

原因不难理解，显然 $a_i-\lfloor \frac{a_i}{d}\rfloor$ 单调不降，如果满足上述条件，显然 $a_i-\lfloor \frac{a_i}{d}\rfloor$ 都相等，那么直接作整体加（实际上是减）即可。

这种操作的复杂度如何？

根据直觉，其实会发现每次 2 操作 $a_i$ 减小得比 $\lfloor\frac{a_i}{d} \rfloor$ 快得多，主观上时间复杂度并不高。

严谨的时间复杂度证明需要势能分析。

（注：此处贺了 LOJ 讨论区的证明，加了点我自己的理解，大概率是错的，看个乐就行）

不妨设 $n,v$ 同阶。

定义势能为 $\sum \log_2 (|a_i-a_{i-1}|)$。

显然，开始时势能为 $O(n\log n)$。

一次区间加后，区间 $[l,r]$ 内部势能不变，两端各增加 $O(\log_2 n)$。总体来说变化量可以忽略（其实此时的势能为 $O((n+q)\log_2 n)$）。

每个势能的连续段在树上被分为 $\log$ 段，而每次区间除法操作珂以使两个相邻连续段之间的势能减 1。

相当于用 $\log$ 的代价减去了 1。

那么总的时间复杂度即为 $O((n+q)\log ^2 n)$。

#include <bits/stdc++.h>
typedef long long ll;
const ll INF = 1e18;

int read() {
    int s = 0,f = 1;
    char c = getchar();
    for(;c < '0'||c > '9';c = getchar())
        if(c == '-')f = -1;
    for(;c >= '0'&&c <= '9';c = getchar())
        s = (s << 1) + (s << 3) + (c ^ '0');
    return s * f;
}

const int maxn = 1e5 + 5;
int n,m;

int ls[maxn << 2],rs[maxn << 2];
ll sum[maxn << 2],lz[maxn << 2],maxv[maxn << 2],minv[maxn << 2];

void pushup(int i) {
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
    maxv[i] = std::max(maxv[i << 1] , maxv[i << 1 | 1]);
    minv[i] = std::min(minv[i << 1] , minv[i << 1 | 1]);
    return ;
}

void pushdown(int i) {
    if(!lz[i])return ;
    lz[i << 1] += lz[i];
    lz[i << 1 | 1] += lz[i];
    minv[i << 1] += lz[i];
    minv[i << 1 | 1] += lz[i];
    maxv[i << 1] += lz[i];
    maxv[i << 1 | 1] += lz[i];
    sum[i << 1] += 1ll * (rs[i << 1] - ls[i << 1] + 1) * lz[i];
    sum[i << 1 | 1] += 1ll * (rs[i << 1 | 1] - ls[i << 1 | 1] + 1) * lz[i];
    lz[i] = 0;
    return ;
}

void build(int i,int l,int r) {
    ls[i] = l;
    rs[i] = r;
    if(l == r) {
        sum[i] = maxv[i] = minv[i] = read();
        return ;
    }
    int mid = l + r >> 1;
    build(i << 1 , l , mid);
    build(i << 1 | 1 , mid + 1 , r);
    pushup(i);
    return ;
}

void modify(int i,int l,int r,int k) {
    if(ls[i] >= l&&rs[i] <= r) {
        sum[i] += 1ll * k * (rs[i] - ls[i] + 1);
        lz[i] += k;
        maxv[i] += k;
        minv[i] += k;
        return ;
    }
    if(ls[i] > r||rs[i] < l)return ;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    if(l <= mid)modify(i << 1 , l , r , k);
    if(r > mid)modify(i << 1 | 1 , l , r , k);
    pushup(i);
    return ;
}

void Maintain(int i,int l,int r,int k) {
    if(ls[i] >= l&&rs[i] <= r) {
        int x = maxv[i] - (int)std::floor((double)(1.0 * (double)maxv[i] / (double)k));
        int y = minv[i] - (int)std::floor((double)(1.0 * (double)minv[i] / (double)k));
        if(x == y) {
            sum[i] -= 1ll * (rs[i] - ls[i] + 1) * x;
            lz[i] -= x;
            maxv[i] -= x;
            minv[i] -= x;
            return ;
        }
    }
    if(ls[i] > r||rs[i] < l)return ;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    if(l <= mid)Maintain(i << 1 , l , r , k);
    if(r > mid)Maintain(i << 1 | 1 , l , r , k);
    pushup(i);
    return ;
}

ll Querymin(int i,int l,int r) {
    if(ls[i] >= l&&rs[i] <= r)return minv[i];
    if(ls[i] > r||rs[i] < l)return INF;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    ll s = INF;
    if(l <= mid)s = std::min(s , Querymin(i << 1 , l , r));
    if(r > mid)s = std::min(s , Querymin(i << 1 | 1 , l , r));
    return s;
}

ll Querysum(int i,int l,int r) {
    if(ls[i] >= l&&rs[i] <= r)return sum[i];
    if(ls[i] > r||rs[i] < l)return 0;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    ll s = 0;
    if(l <= mid)s += Querysum(i << 1 , l , r);
    if(r > mid)s += Querysum(i << 1 | 1 , l , r);
    return s;
}

int main() {
    n = read();
    m = read();

    build(1 , 1 , n);

    while(m --) {
        int op = read(),l = read() + 1,r = read() + 1,k;
        switch(op) {
            case 1: {
                k = read();
                modify(1 , l , r , k);
                break ;
            }
            case 2: {
                k = read();
                Maintain(1 , l , r , k);
                break ;
            }
            case 3: {
                printf("%lld\n",Querymin(1 , l , r));
                break ;
            }
            case 4: {
                printf("%lld\n",Querysum(1 , l , r));
                break ;
            }
        }
    }
    return 0;
}