// #define DEBUGGING #include using namespace std; #define endl '\n' #define ALL(V) (V).begin(), (V).end() #define ALLR(V) (V).rbegin(), (V).rend() template using V = vector; template using VV = V>; using ll = int64_t; using ull = uint64_t; using PLL = pair; template const T& var_min(const T &t) { return t; } template const T& var_max(const T &t) { return t; } template const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); } template const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); } template void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); } template void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); } template const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); } template void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); } namespace init__ { struct InitIO { InitIO() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(30); } } init_io; } #ifdef DEBUGGING // #include "../debug/debug.cpp" #include "../../debug/debug.cpp" #else #define DEBUG(...) 0 #define DEBUG_SEPARATOR_LINE 0 #endif template T make_v(T init) { return init; } template auto make_v(T init, size_t s, Tail... tail) { #define rec make_v(init, tail...) return V(s, rec); #undef rec } template class LazySegmentTree{ private: ll N; T init_node; L init_lazy; vector node; vector lazy; vector lazy_flag; function merge_node; function apply_lazy_value; function update_lazy_value; function create_lazy_value; function prop_lazy_value; public: LazySegmentTree(const vector &v, const T &init_node, const L &init_lazy, const decltype(merge_node) &merge_node, const decltype(apply_lazy_value) &apply_lazy_value, const decltype(update_lazy_value) &update_lazy_value, const decltype(create_lazy_value) &create_lazy_value, const decltype(prop_lazy_value) &prop_lazy_value = [](L v) { return v; }) : init_node(init_node), init_lazy(init_lazy), merge_node(merge_node), apply_lazy_value(apply_lazy_value), update_lazy_value(update_lazy_value), create_lazy_value(create_lazy_value), prop_lazy_value(prop_lazy_value) { ll tmp = 1; while(tmp < v.size()) tmp *= 2; N = tmp; node.resize(2 * N - 1, init_node); lazy.resize(2 * N - 1, init_lazy); lazy_flag.resize(2 * N - 1, false); for(ll i = 0; i < v.size(); i++) { node[i + N - 1] = v[i]; } for(ll i = N - 2; 0 <= i; i--) { node[i] = merge_node(node[i * 2 + 1], node[i * 2 + 2]); } } /* * node[pos] -> [left, right) */ void lazy_eval(ll pos, ll left, ll right) { if(!lazy_flag[pos]) { return; } node[pos] = apply_lazy_value(node[pos], lazy[pos]); lazy_flag[pos] = false; /* * whether the node is the bottom of tree or not. */ if(right - left > 1) { for(ll idx = 2 * pos + 1; idx <= 2 * pos + 2; idx++) { lazy[idx] = update_lazy_value(lazy[idx], prop_lazy_value(lazy[pos])); lazy_flag[idx] = true; } } lazy[pos] = init_lazy; } /* * If you want to call this func from out of class, in many cases you don't have to change the args pos, node_left, node_right. * Be careful that the range is half-open interval. * [left, right), [node_left, node_right) * @param left: lower limit of interval of query * @param right: upper limit of interval of query * @param val: the value gave from query * @param node_left: lower limit of interval of the node points. * @param node_right: upper limit of interval of the node points. */ void update_query(ll left, ll right, L val, ll pos = 0, ll node_left = 0, ll node_right = -1) { if(node_right < 0) { node_right = N; } /* * Execute lazy evaluation. */ lazy_eval(pos, node_left, node_right); /* * If the node is out of inrerval, return. */ if(right <= node_left || node_right <= left) { return; } /* * If the node cover the interval complety, update this->lazy and execute lazy_eval. * Else recursion. */ if(left <= node_left && node_right <= right) { lazy[pos] = create_lazy_value(node_left, node_right, val); lazy_flag[pos] = true; lazy_eval(pos, node_left, node_right); } else { /* * recursion */ update_query(left, right, val, 2 * pos + 1, node_left, (node_left + node_right) / 2); update_query(left, right, val, 2 * pos + 2, (node_left + node_right) / 2, node_right); node[pos] = merge_node(node[2 * pos + 1], node[2 * pos + 2]); } } T get_query(ll left, ll right, ll pos = 0, ll node_left = 0, ll node_right = -1) { if(node_right < 0) { node_right = N; } /* * Evaluate the node[pos] */ lazy_eval(pos, node_left, node_right); if(node_right <= left || right <= node_left) { return init_node; } if(left <= node_left && node_right <= right) { return node[pos]; } ll split = (node_left + node_right) / 2; return merge_node(get_query(left, right, 2 * pos + 1, node_left, split), get_query(left, right, 2 * pos + 2, split, node_right)); } }; using TLL = tuple; const ll inf = 5e15; int main() { ll N, Q; cin >> N >> Q; V A(N); for(ll i = 0; i < N; i++) { ll e; cin >> e; A[i] = TLL(e, 0, e); } LazySegmentTree lst(A, TLL(inf, 0, inf), 0, [](TLL t, TLL u) { ll a, b, c, d, e, f; tie(a, b, c) = t; tie(d, e, f) = u; DEBUG(make_tuple(t, u)); return TLL(a, b + e + (c != d && c != inf && d != inf), f); }, [](TLL t, ll v) { ll a, b, c; tie(a, b, c) = t; DEBUG(make_tuple(t, v)); return TLL(a + v, 0, c + v); }, [](ll a, ll b) { return a + b; }, [](ll l, ll r, ll v) { return v; }); while(Q--) { ll q, l, r; cin >> q >> l >> r; l--; if(q == 1) { ll x; cin >> x; lst.update_query(l, r, x); } else { cout << get<1>(lst.get_query(l, r)) + 1 << endl; } } return 0; }