#line 1 ".lib/template.hpp" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define allof(obj) (obj).begin(), (obj).end() #define range(i, l, r) for(int i=l;i>1)|y_bit)) #define bit_kth(i, k) ((i >> k)&1) #define bit_highest(i) (i?63-__builtin_clzll(i):-1) #define bit_lowest(i) (i?__builtin_ctzll(i):-1) #define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t)) using ll = long long; using ld = long double; using ul = uint64_t; using pi = std::pair; using pl = std::pair; using namespace std; template std::ostream &operator<<(std::ostream &dest, const std::pair &p){ dest << p.first << ' ' << p.second; return dest; } template std::ostream &operator<<(std::ostream &dest, const std::vector> &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::vector &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::array &v){ if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::set &v){ for(auto itr=v.begin();itr!=v.end();){ dest << *itr; itr++; if(itr!=v.end()) dest << ' '; } return dest; } template std::ostream &operator<<(std::ostream &dest, const std::map &v){ for(auto itr=v.begin();itr!=v.end();){ dest << '(' << itr->first << ", " << itr->second << ')'; itr++; if(itr!=v.end()) dest << '\n'; } return dest; } std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } template vector make_vec(size_t sz, T val){return std::vector(sz, val);} template auto make_vec(size_t sz, Tail ...tail){ return std::vector(tail...))>(sz, make_vec(tail...)); } template vector read_vec(size_t sz){ std::vector v(sz); for(int i=0;i<(int)sz;i++) std::cin >> v[i]; return v; } template auto read_vec(size_t sz, Tail ...tail){ auto v = std::vector(tail...))>(sz); for(int i=0;i<(int)sz;i++) v[i] = read_vec(tail...); return v; } void io_init(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } #line 2 "a.cpp" template struct segment_tree_beats{ using Val = typename beats_struct::Val; using Lazy = typename beats_struct::Lazy; int N, M; std::vector val; std::vector lazy; std::vector is_id; void push_down(int k, int l, int r){ if(M - 1 <= k || is_id[k]) return; int mid = (l + r) >> 1; propagate(k * 2 + 1, l, mid, lazy[k]); propagate(k * 2 + 2, mid, r, lazy[k]); is_id[k] = true; } void propagate(int k, int l, int r, const Lazy &x){ if(k < M - 1){ if(is_id[k]){ lazy[k] = x; is_id[k] = false; }else{ beats_struct::propagate_lazy(lazy[k], x); } } beats_struct::apply(val[k], x, l, r); } void set(int a, Val x, int k, int l, int r){ if(r - l == 1){ val[k] = x; return; } push_down(k, l, r); int mid = (l + r) >> 1; if(a < mid) set(a, x, k * 2 + 1, l, mid); else set(a, x, k * 2 + 2, mid, r); beats_struct::merge_val(val[k], val[k * 2 + 1], val[k * 2 + 2]); } void get(int a, int k, int l, int r, Val &ans){ if(r - l == 1){ ans = val[k]; return; } push_down(k, l, r); int mid = (l + r) >> 1; if(a < mid) get(a, k * 2 + 1, l, mid, ans); else get(a, k * 2 + 2, mid, r, ans); } template void update(int a, int b, const Lazy &x, int k, int l, int r){ if(r <= a || b <= l || beats_struct::template break_check(val[k], x)) return; /* if(a <= l && r <= b && beats_struct::template tag_check(val[k], x)){ propagate(k, l, r, x); return; } */ if(a <= l && r <= b && beats_struct::template tag_check(val[k], x)){ if(id == 0){ propagate(k, l, r, x); }else{ Lazy y(std::gcd(val[k].g, x.setx)); propagate(k, l, r, y); } return; } push_down(k, l, r); update(a, b, x, k * 2 + 1, l, (l + r) / 2); update(a, b, x, k * 2 + 2, (l + r) / 2, r); beats_struct::merge_val(val[k], val[k * 2 + 1], val[k * 2 + 2]); } void query(int a, int b, int k, int l, int r, Val &ans){ if(r <= a || b <= l) return; if(a <= l && r <= b){ Val tmp = beats_struct::id_val(); beats_struct::merge_val(tmp, ans, val[k]); ans = tmp; return; } push_down(k, l, r); query(a, b, k * 2 + 1, l, (l + r) / 2, ans); query(a, b, k * 2 + 2, (l + r) / 2, r, ans); } int c2(int x){ int y = 1; while(y < x) y <<= 1; return y; } segment_tree_beats(): N(0), M(0){} template segment_tree_beats(const std::vector &v): N(v.size()), M(c2(N)), val(2 * M - 1, Val()), lazy(M - 1, Lazy()), is_id(M - 1, true){ for(int i = 0; i < N; i++) val[M - 1 + i] = Val(v[i]); for(int i = N; i < M; i++) val[M - 1 + i] = beats_struct::id_val(); for(int i = M - 2; i >= 0; i--) beats_struct::merge_val(val[i], val[i * 2 + 1], val[i * 2 + 2]); } template void update(int l, int r, Lazy x){ update(l, r, x, 0, 0, M); } Val query(int l, int r){ Val ans = beats_struct::id_val(); query(l, r, 0, 0, M, ans); return ans; } }; template struct add_chmin_chmax{ static constexpr T inf = std::numeric_limits::max(); static constexpr T minf = std::numeric_limits::min(); struct Val{ T min, second_min, max, second_max, sum; int min_cnt, max_cnt; Val(): min(inf), second_min(inf), max(minf), second_max(minf), sum(0), min_cnt(0), max_cnt(0){} Val(T x): min(x), second_min(inf), max(x), second_max(minf), sum(x), min_cnt(1), max_cnt(1){} }; struct Lazy{ T add, lower, upper; Lazy(): add(0), lower(minf), upper(inf){} Lazy(T a, T b, T c): add(a), lower(b), upper(c){} }; static Val id_val(){ return Val(); } // l, rをマージしてvに代入 static void merge_val(Val &v, const Val &l, const Val &r){ v.sum = l.sum + r.sum; if(l.max == r.max){ v.max = l.max; v.max_cnt = l.max_cnt + r.max_cnt; v.second_max = std::max(l.second_max, r.second_max); }else if(l.max > r.max){ v.max = l.max; v.max_cnt = l.max_cnt; v.second_max = std::max(l.second_max, r.max); }else{ v.max = r.max; v.max_cnt = r.max_cnt; v.second_max = std::max(l.max, r.second_max); } if(l.min == r.min){ v.min = l.min; v.min_cnt = l.min_cnt + r.min_cnt; v.second_min = std::min(l.second_min, r.second_min); }else if(l.min < r.min){ v.min = l.min; v.min_cnt = l.min_cnt; v.second_min = std::min(l.second_min, r.min); }else{ v.min = r.min; v.min_cnt = r.min_cnt; v.second_min = std::min(l.min, r.second_min); } } static void apply(Val &a, const Lazy &b, int l, int r){ if(b.add){ a.min += b.add; if(a.second_min != inf) a.second_min += b.add; a.max += b.add; if(a.second_max != minf) a.second_max += b.add; a.sum += b.add * (r - l); } if(a.min < b.lower){ a.sum += (b.lower - a.min) * a.min_cnt; if(a.second_max == a.min) a.second_max = b.lower; else if(a.max == a.min) a.max = b.lower, a.second_max = minf; a.min = b.lower; } if(b.upper < a.max){ a.sum -= (a.max - b.upper) * a.max_cnt; if(a.second_min == a.max) a.second_min = b.upper; else if(a.min == a.max) a.min = b.upper, a.second_min = inf; a.max = b.upper; } } static void propagate_lazy(Lazy &a, const Lazy &b){ if(b.add){ a.add += b.add; if(a.lower != minf) a.lower += b.add; if(a.upper != inf) a.upper += b.add; } if(a.upper <= b.lower) a.lower = a.upper = b.lower; else if(b.upper <= a.lower) a.lower = a.upper = b.upper; else{ a.lower = std::max(a.lower, b.lower); a.upper = std::min(a.upper, b.upper); } } // chmin template* = nullptr> static bool break_check(const Val &v, const Lazy &x){ return v.max < x.upper; } template* = nullptr> static bool tag_check(const Val &v, const Lazy &x){ return v.second_max < x.upper; } // chmax template* = nullptr> static bool break_check(const Val &v, const Lazy &x){ return v.min > x.lower; } template* = nullptr> static bool tag_check(const Val &v, const Lazy &x){ return v.second_min > x.lower; } // add template* = nullptr> static bool break_check(const Val &v, const Lazy &x){ return false; } template* = nullptr> static bool tag_check(const Val &v, const Lazy &x){ return true; } }; template struct abc256ex_set_div_sum{ static constexpr T minf = std::numeric_limits::min(); struct Val{ T sum, unique; // unique != minfなら区間がその値でユニーク Val(): sum(0), unique(minf){} Val(T x): sum(x), unique(x){} }; struct Lazy{ T setx; Lazy(): setx(minf){} Lazy(T x): setx(x){} /* update関数を書き換える if(a <= l && r <= b && beats_struct::template tag_check(val[k], x)){ if(id == 0){ propagate(k, l, r, x); }else{ Lazy y(val[k].unique / x.setx); propagate(k, l, r, y); } return; } */ }; static Val id_val(){ return Val(); } // l, rをマージしてvに代入 static void merge_val(Val &v, const Val &l, const Val &r){ v.sum = l.sum + r.sum; if(l.unique == r.unique) v.unique = l.unique; else v.unique = minf; } static void apply(Val &a, const Lazy &b, int l, int r){ a.sum = b.setx * (r - l); a.unique = b.setx; } static void propagate_lazy(Lazy &a, const Lazy &b){ a = b; } // set template* = nullptr> static bool break_check(const Val &v, const Lazy &x){ return false; } template* = nullptr> static bool tag_check(const Val &v, const Lazy &x){ return true; } // div template* = nullptr> static bool break_check(const Val &v, const Lazy &x){ return v.unique == 0; } template* = nullptr> static bool tag_check(const Val &v, const Lazy &x){ return v.unique != minf; } }; template struct yuki880_set_gcd_min_sum{ static constexpr T minf = std::numeric_limits::min(); struct Val{ T sum, max, g; Val(): sum(0), max(minf), g(0){} Val(T x): sum(x), max(x), g(x){} }; struct Lazy{ T setx; Lazy(): setx(0){} Lazy(T x): setx(x){} /* update関数を書き換える if(a <= l && r <= b && beats_struct::template tag_check(val[k], x)){ if(id == 0){ propagate(k, l, r, x); }else{ Lazy y(std::gcd(val[k].g, x.setx)); propagate(k, l, r, y); } return; } */ }; static Val id_val(){ return Val(); } // l, rをマージしてvに代入 static void merge_val(Val &v, const Val &l, const Val &r){ v.sum = l.sum + r.sum; v.max = std::max(l.max, r.max); v.g = std::gcd(l.g, r.g); } static void apply(Val &a, const Lazy &b, int l, int r){ a.sum = b.setx * (r - l); a.max = a.g = b.setx; } static void propagate_lazy(Lazy &a, const Lazy &b){ a = b; } // set template* = nullptr> static bool break_check(const Val &v, const Lazy &x){ return false; } template* = nullptr> static bool tag_check(const Val &v, const Lazy &x){ return true; } // gcd template* = nullptr> static bool break_check(const Val &v, const Lazy &x){ return v.g == 0 || std::gcd(v.g, x.setx) == x.setx; } template* = nullptr> static bool tag_check(const Val &v, const Lazy &x){ return v.g == v.max; } }; int main(){ io_init(); int n, q; std::cin >> n >> q; auto a = read_vec(n); segment_tree_beats> seg(a); for(int i = 0; i < q; i++){ long long x, y, z, v; std::cin >> x >> y >> z; y--; if(x == 3){ std::cout << seg.query(y, z).max << '\n'; }else if(x == 4){ std::cout << seg.query(y, z).sum << '\n'; }else{ std::cin >> v; if(x == 1){ seg.update<0>(y, z, {v}); }else if(x == 2){ seg.update<1>(y, z, {v}); } } } }