The Child and The Sequence

#include <bits/stdc++.h>

using namespace std;

#define long long long int

struct SegmentTreeBeats {
private:
    struct Node {
        int mn, mx;
        long sum;

        Node(): mn(0), mx(0), sum(0LL) {}
        Node(int mn, int mx, long sum): mn(mn), mx(mx), sum(sum) {}

        Node operator +(Node other) {
            return Node(min(mn, other.mn), max(mx, other.mx), sum + other.sum);
        }
    };

    int n;
    vector<int> a;
    vector<Node> tree;
    vector<int> lazy;

public:
    SegmentTreeBeats(int n, vector<int> &a) {
        this->n = n;
        this->a = a;

        tree.resize(4 * n);
        lazy.assign(4 * n, -1);

        build(1, 1, n);
    }

    void update(int i, int x) {
        update(1, 1, n, i, x);
    }

    void update(int l, int r, int x) {
        update(1, 1, n, l, r, x);
    }

    long query(int l, int r) {
        return query(1, 1, n, l, r);
    }

private:
    void build(int node, int l, int r) {
        if (l == r) tree[node] = Node(a[l], a[l], a[l]);
        else {
            int mid = (l + r) / 2;
            build(2 * node, l, mid);
            build(2 * node + 1, mid + 1, r);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    void update_lazy(int node, int l, int r, int x) {
        assert(tree[node].mx == tree[node].mn);

        tree[node].mx = tree[node].mn = x;
        tree[node].sum = (r - l + 1LL) * x;
        lazy[node] = x;
    }

    void push_down(int node, int l, int r) {
        if (lazy[node] == -1) return;

        int mid = (l + r) / 2;
        update_lazy(2 * node, l, mid, lazy[node]);
        update_lazy(2 * node + 1, mid + 1, r, lazy[node]);
        lazy[node] = -1;
    }

    void update(int node, int l, int r, int i, int x) {
        if (l == r) tree[node] = Node(x, x, x);
        else {
            push_down(node, l, r);

            int mid = (l + r) / 2;
            if (i <= mid) update(2 * node, l, mid, i, x);
            else update(2 * node + 1, mid + 1, r, i, x);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    void update(int node, int l, int r, int ul, int ur, int x) {
        if (r < ul || l > ur || tree[node].mx < x) return;
        if (ul <= l && r <= ur && tree[node].mx == tree[node].mn) {
            update_lazy(node, l, r, tree[node].mx % x);
            return;
        }

        push_down(node, l, r);

        int mid = (l + r) / 2;
        update(2 * node, l, mid, ul, ur, x);
        update(2 * node + 1, mid + 1, r, ul, ur, x);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    long query(int node, int l, int r, int ql, int qr) {
        if (r < ql || l > qr) return 0LL;
        if (ql <= l && r <= qr) return tree[node].sum;

        push_down(node, l, r);

        int mid = (l + r) / 2;
        return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    SegmentTreeBeats tree(n, a);
    while (m--) {
        int op; cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;

            long ans = tree.query(l, r);
            cout << ans << "\n";
        } else if (op == 2) {
            int l, r, x;
            cin >> l >> r >> x;
            tree.update(l, r, x);
        } else {
            int k, x;
            cin >> k >> x;
            tree.update(k, x);
        }
    }
}