// need #include #include // data structure #include #include #include #include #include #include #include #include #include //#include #include #include #include #include // etc #include #include #include #include #include #include #include // input #define INIT std::ios::sync_with_stdio(false);std::cin.tie(0); #define VAR(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__); template void MACRO_VAR_Scan(T& t) { std::cin >> t; } templatevoid MACRO_VAR_Scan(First& first, Rest& ...rest) { std::cin >> first; MACRO_VAR_Scan(rest...); } #define VEC_ROW(type, n, ...)std::vector __VA_ARGS__;MACRO_VEC_ROW_Init(n, __VA_ARGS__); for(int w_=0; w_ void MACRO_VEC_ROW_Init(int n, T& t) { t.resize(n); } templatevoid MACRO_VEC_ROW_Init(int n, First& first, Rest& ...rest) { first.resize(n); MACRO_VEC_ROW_Init(n, rest...); } template void MACRO_VEC_ROW_Scan(int p, T& t) { std::cin >> t[p]; } templatevoid MACRO_VEC_ROW_Scan(int p, First& first, Rest& ...rest) { std::cin >> first[p]; MACRO_VEC_ROW_Scan(p, rest...); } #define VEC(type, c, n) std::vector c(n);for(auto& i:c)std::cin>>i; #define MAT(type, c, m, n) std::vector> c(m, std::vector(n));for(auto& R:c)for(auto& w:R)std::cin>>w; // output #define OUT(dist) std::cout<<(dist); #define FOUT(n, dist) std::cout<=(a);--w) #define REP(w, n) for(int w=0;w=0;--w) #define IN(a, x, b) (a<=x && x inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; } template inline T CHMIN(T& a, const T b) { return a = (a > b) ? b : a; } // test template using V = std::vector; template using VV = V>; template std::ostream& operator<<(std::ostream& os, std::pair p) { os << "(" << p.first << ", " << p.second << ")"; return os; } #define random_shuffle "USE std::shuffle!"; // type/const //#define int ll using ll = long long; using ull = unsigned long long; using ld = long double; using PAIR = std::pair; using PAIRLL = std::pair; constexpr int INFINT = (1 << 30) - 1; // 1.07x10^ 9 constexpr int INFINT_LIM = (1LL << 31) - 1; // 2.15x10^ 9 constexpr ll INFLL = 1LL << 60; // 1.15x10^18 constexpr ll INFLL_LIM = (1LL << 62) - 1 + (1LL << 62); // 9.22x10^18 constexpr double EPS = 1e-10; constexpr int MOD = 1000000007; constexpr double PI = 3.141592653589793238462643383279; template void FILL(T(&a)[N], const T & val) { for (auto& x : a) x = val; } template void FILL(ARY(&a)[N][M], const T & val) { for (auto& b : a) FILL(b, val); } template void FILL(std::vector & a, const T & val) { for (auto& x : a) x = val; } template void FILL(std::vector> & a, const T & val) { for (auto& b : a) FILL(b, val); } // ------------>8------------------------------------->8------------ // ------------>8------------ SegmentTree ------------>8------------ namespace Monoid { template class sum { public: using value_type = T; inline static T operation(const T& a, const T& b) { return a + b; } inline static T identity() { return T(0); } }; template class max { public: using value_type = T; inline static T operation(const T& a, const T& b) { return (a < b) ? b : a; } inline static T identity() { return std::numeric_limits::lowest(); } }; template class min { public: using value_type = T; inline static T operation(const T& a, const T& b) { return (a < b) ? a : b; } inline static T identity() { return std::numeric_limits::max(); } }; class MONOID { public: struct S { int x; }; using value_type = S; inline static S operation(const S& l, const S& r) { return S{ l.x + r.x }; } inline static S identity() { return S{ 0 }; } }; } template class SegmentTree { private: using T = typename Monoid::value_type; int ARY_SIZE; std::vector ary; void init(int n) { while (ARY_SIZE < n) ARY_SIZE <<= 1; ary.resize(ARY_SIZE << 1, Monoid::identity()); } public: SegmentTree(int n) : ARY_SIZE(1) { init(n); } SegmentTree(std::vector& a) : ARY_SIZE(1) { init(a.size()); std::copy(a.begin(), a.end(), ary.begin() + ARY_SIZE); for (int i = ARY_SIZE - 1; i >= 1; --i) { ary[i] = Monoid::operation(ary[i << 1], ary[(i << 1) + 1]); } } // -- a[i] = val; inline void update(int i, T val) { i += ARY_SIZE; ary[i] = val; while (i > 1) { i >>= 1; ary[i] = Monoid::operation(ary[i << 1], ary[(i << 1) + 1]); } } // -- a[i] += val; inline void add(int i, T val) { update(i, ary[i + ARY_SIZE] + val); } // -- [l, r) inline T query(int l, int r) { if (l >= r) return Monoid::identity(); T vl = Monoid::identity(), vr = Monoid::identity(); for (l += ARY_SIZE, r += ARY_SIZE; l != r; l >>= 1, r >>= 1) { if (l & 1) vl = Monoid::operation(vl, ary[l++]); if (r & 1) vr = Monoid::operation(ary[--r], vr); } return Monoid::operation(vl, vr); } T operator[](int i) { return ary[i + ARY_SIZE]; } void debugShow() { for (int i = ARY_SIZE; i < ARY_SIZE << 1; ++i) std::cerr << ary[i] << " "; std::cerr << "\n"; } }; // ------------8<------------ SegmentTree ------------8<------------ signed main() { INIT; VAR(int, n, Q); VEC(int, a, n); V b(n - 1); SegmentTree> st(n); REP(i, n - 1) { b[i] = a[i + 1] - a[i]; st.update(i, b[i] != 0); } REP(_, Q) { VAR(int, ty, l, r); --l, --r; if (ty == 1) { VAR(int, x); if (l > 0) { b[l - 1] += x; st.update(l - 1, b[l - 1] != 0); } if (r < n - 1) { b[r] -= x; st.update(r, b[r] != 0); } } else { OUT(st.query(l, r) + 1)BR; } } return 0; }