#include #include #include using namespace std; using lint = long long int; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); }; } fast_ios_; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i istream &operator>>(istream &is, vector &vec){ for (auto &v : vec) is >> v; return is; } ///// This part below is only for debug, not used ///// template ostream &operator<<(ostream &os, const vector &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const pair &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; } #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; ///// END ///// constexpr lint INF = 1e9 + 100; struct Node { int n; lint max_val; lint total_sum; lint lca; Node(int n = 0, int max_val = 0, lint total_sum = 0, lint lca = 1) : n(n), max_val(max_val), total_sum(total_sum), lca(lca) {} }; constexpr int UPDATE = 1; constexpr int GCD = 2; constexpr int MAXVAL = 3; constexpr int SUM = 4; struct LazySegTree { using T_NODE = Node; using T_DELAY = plint; // using T_QUERY = lint; using T_RETVAL = plint; T_NODE zero_node = Node(); T_DELAY zero_delay = plint(0, 0); T_RETVAL zero_retval = plint(0, 0); int N; int head; vector vvalue; vector vdelay; void merge_node(int pos) { int l = pos * 2 + 1, r = pos * 2 + 2; // Here, you have to calculate vvalue[pos] from children (vvalue[l], vvalue[r]), // with assumptions `vdelay[pos] = vdelay[l] = vdelay[r] = zero_delay` vvalue[pos].n = vvalue[l].n + vvalue[r].n; vvalue[pos].max_val = max(vvalue[l].max_val, vvalue[r].max_val); vvalue[pos].total_sum = vvalue[l].total_sum + vvalue[r].total_sum; vvalue[pos].lca = min(INF, vvalue[l].lca * vvalue[r].lca / __gcd(vvalue[l].lca, vvalue[r].lca)); } void reflect_delay(int pos) { if (pos < head and vdelay[pos] != zero_delay) { pushdown_dval(pos * 2 + 1, vdelay[pos]); pushdown_dval(pos * 2 + 2, vdelay[pos]); } // Here, you must update vvalue[pos] by reflecting vdelay[pos], without inconsistency if (vdelay[pos].second == UPDATE) { vvalue[pos] = Node(vvalue[pos].n, vdelay[pos].first, vdelay[pos].first * vvalue[pos].n, vdelay[pos].first); } if (vdelay[pos].second == GCD) { if (vvalue[pos].lca < INF and vdelay[pos].first % vvalue[pos].lca == 0) return; if (pos < head) { reflect_delay(pos * 2 + 1); reflect_delay(pos * 2 + 2); merge_node(pos); } else { lint x = vvalue[pos].total_sum; lint xnew = __gcd(x, vdelay[pos].first); vvalue[pos] = Node(1, xnew, xnew, xnew); } } vdelay[pos] = zero_delay; } void pushdown_dval(int child_pos, const T_DELAY &d) { // operate d to vdelay[child_pos] if (d.second == UPDATE or vdelay[child_pos].second == 0) vdelay[child_pos] = d; else if (d.second == GCD) { vdelay[child_pos].first = __gcd(vdelay[child_pos].first, d.first); } } T_RETVAL calc_retval(int pos) { return make_pair(vvalue[pos].max_val, vvalue[pos].total_sum); } T_RETVAL merge_retval(const T_RETVAL &l, const T_RETVAL &r) { return make_pair(max(l.first, r.first), l.second + r.second); } ////// general description ////// LazySegTree(const vector &val_init) : N(val_init.size()) { int N_tmp = 1; while (N_tmp < N) N_tmp <<= 1; vvalue.assign(N_tmp * 2, zero_node); vdelay.assign(N_tmp * 2, zero_delay); head = N_tmp - 1; copy(val_init.begin(), val_init.end(), vvalue.begin() + head); for (int pos = head - 1; pos >= 0; pos--) { merge_node(pos); } } void update(int begin, int end, T_DELAY delay, int pos=0, int l=0, int r=-1) { // Operate delay to the node pos // After this, vdelay[pos] must be zero if (r < 0) r = head + 1; if (begin <= l and r <= end) { // Update whole [l, r) by delay pushdown_dval(pos, delay); reflect_delay(pos); } else if (begin < r and l < end) { // Update somewhere in [l, r) reflect_delay(pos); update(begin, end, delay, pos * 2 + 1, l, (l + r) / 2); update(begin, end, delay, pos * 2 + 2, (l + r) / 2, r); merge_node(pos); } else reflect_delay(pos); } T_RETVAL getvalue(int begin, int end, int pos=0, int l=0, int r=-1) // Get value in [begin, end) { if (r < 0) r = head + 1; reflect_delay(pos); if (begin <= l and r <= end) return calc_retval(pos); else if (begin < r and l < end) { T_RETVAL vl = getvalue(begin, end, pos * 2 + 1, l, (l + r) / 2); T_RETVAL vr = getvalue(begin, end, pos * 2 + 2, (l + r) / 2, r); return merge_retval(vl, vr); } else return zero_retval; } }; int main() { int N, Q; cin >> N >> Q; vector A(N); REP(i, N) { int a; cin >> a; A[i] = Node(1, a, a, a); } LazySegTree st(A); REP(_, Q) { int q, l, r; cin >> q >> l >> r; l--; if (q == UPDATE) { lint x; cin >> x; st.update(l, r, plint(x, UPDATE)); } if (q == GCD) { lint x; cin >> x; st.update(l, r, plint(x, GCD)); } if (q == MAXVAL) { cout << st.getvalue(l, r).first << endl; } if (q == SUM) { cout << st.getvalue(l, r).second << endl; } } }