题目

现在有一个数列A，共有N个数字。现在有Q次操作，每次有3个选择
当type为1时，需要将L到R中的每一个数字向下整除X
当type为2时，需要将L到R中的每一个数字替换成Y
当type为3时，需要求出L到R中的数字的和

输入格式

第一行有两个整数 N 和 Q,第二行有N个整数，是数列A，接下来的Q行操作，有3至4个整数，根据type改变

数据范围：

1<=N<=5*1e5 , 1<=Q<=1e5 , 1<=L<=R<=N ,1<=A(i)<=1e5 , 2<=x<=1e5 , 1<=y<=1e5 

输出格式

对于每一个询问3输出一个整数

输入/输出例子1

输入：

3 5

2 5 6

3 1 3

1 2 3 2

3 1 2

2 1 2 3

3 1 3

输出：

13

4

9

输入/输出例子2

输入：

6 11

10 3 5 20 6 7

3 1 6

1 2 4 3

3 1 3

2 1 4 10

3 3 6

1 3 6 2

2 1 4 5

3 1 6

2 1 3 100

1 2 5 6

3 1 4

输出：

51

12

33

26

132

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 5e6 + 20;
ll nul = -1e7 - 20;
ll n, q, a[N], op, x, y, k;
ll w[N], t1[N], t2[N];
inline ll ls(ll x) {return x << 1;}
inline ll rs(ll x) {return x << 1 | 1;}
ll build(ll p, ll l, ll r) {
    if (l == r) {
        w[p] = a[l];
        return w[p];
    }
    ll mid = (l + r) >> 1;
    w[p] = build(ls(p), l, mid) + build(rs(p), mid + 1, r);
    return w[p];
}
void down(ll p, ll l, ll r) {
    ll mid = (l + r) >> 1;
    if (t1[p] != nul) {
        w[ls(p)] = t1[p] * (mid - l + 1);
        w[rs(p)] = t1[p] * (r - mid);
        t1[ls(p)] = t1[rs(p)] = t1[p];
        t2[ls(p)] = t2[rs(p)] = 1;
        t1[p] = nul;
    }
    else if (t2[p] != 1) {
        w[ls(p)] /= t2[p];
        w[rs(p)] /= t2[p];
        if (t1[ls(p)] != nul) t1[ls(p)] /= t2[p];
        else t2[ls(p)] *= t2[p];
        if (t1[rs(p)] != nul) t1[rs(p)] /= t2[p];
        else t2[rs(p)] *= t2[p];
        t2[p] = 1;
    }
}
void up(ll p) {
    w[p] = w[ls(p)] + w[rs(p)];
}
void change(ll p, ll l, ll r, ll x, ll y, ll k) {
    if (x <= l && r <= y) {
        w[p] = (r - l + 1) * k;
        t1[p] = k;
        t2[p] = 1;
        return ;
    }
    down(p, l, r);
    ll mid = (l + r) >> 1;
    if (x <= mid) change(ls(p), l, mid, x, y, k);
    if (y  > mid) change(rs(p), mid + 1, r, x, y, k);
    up(p);
}
void add(ll p, ll l, ll r, ll x, ll y, ll k) {
    if (x <= l && r <= y) {
        w[p] /= k;
        if (t1[p] != nul) t1[p] /= k;
        else t2[p] *= k;
        return ;
    }
    down(p, l, r);
    ll mid = (l + r) >> 1;
    if (x <= mid) add(ls(p), l, mid, x, y, k);
    if (y  > mid) add(rs(p), mid + 1, r, x, y, k);
    up(p);
}
ll ask(int p, int l, int r, int x, int y) {
    ll ans = 0;
    if (x <= l && r <= y) return w[p];
    down(p, l, r);
    int mid = (l + r) >> 1;
    if (  x  <=  mid)   ans += ask(ls(p),  l    , mid, x, y);
    if (  y  >   mid)   ans += ask(rs(p), mid + 1, r,   x, y);
    return ans;
}
int main(){
    for (int i = 0; i < 5 * 1e6; i++) t1[i] = nul, t2[i] = 1;
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        scanf("%lld%lld%lld", &op, &x, &y);
        if (op != 3) scanf("%lld", &k);
        if (op == 1) add(1, 1, n, x, y, k);
        if (op == 2) {
            change(1, 1, n, x, y, k);
        }
        if (op == 3) printf("%lld\n", ask(1, 1, n, x, y));
    }
    return 0;
}