#line 2 "Library/src/data-structure/BIT.hpp" #include namespace kyopro { template class BIT { std::vector bit; int n; public: BIT() : BIT(0) {} BIT(int n) : n(n), bit(n + 1, T()) {} void add(int p, T w) { p++; for (int x = p; x <= n; x += x & -x) { bit[x] += w; } } T sum(int p) const { T s = 0; for (int x = p; x > 0; x -= x & -x) { s += bit[x]; } return s; } T sum(int l, int r) const { return sum(r) - sum(l); } int lower_bound(T w) const { if (w <= 0) return 0; int x = 0; int k = 1; while (k < n) k <<= 1; for (; k > 0; k >>= 1) { if (x + k <= n && bit[x + k] < w) { w -= bit[x + k]; x += k; } } return x + 1; } T operator[](int i) { return sum(i + 1) - sum(i); } void update(int i, T v) { add(i, -(*this)[i] + v); } }; }; // namespace kyopro /** * @brief Binary Index Tree */ #line 2 "Library/src/data-structure/dual_segtree.hpp" #include #line 4 "Library/src/data-structure/dual_segtree.hpp" namespace kyopro { template class dual_segtree { std::vector dat; int _n, sz, lg; public: dual_segtree() : dual_segtree(0) {} dual_segtree(int _n) : _n(_n) { sz = 1, lg = 0; while (sz < _n) { ++lg; sz <<= 1; } dat.assign(sz << 1, id()); } private: void update(int p, const F& v) { dat[p] = composition(dat[p], v); } void push(int p) { if (dat[p] == id()) { return; } update(p << 1 | 0, dat[p]); update(p << 1 | 1, dat[p]); dat[p] = id(); } public: F operator[](int p) { assert(0 <= p && p < _n); p += sz; for (int i = lg; i > 0; i--) { push(p >> i); } return dat[p]; } void apply(int l, int r, const F& v) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += sz, r += sz; for (int i = lg; i > 0; i--) { if (((l >> i) << i) != l) { push(l >> i); } if (((r >> i) << i) != r) { push((r - 1) >> i); } } while (l < r) { if (l & 1) { update(l++, v); } if (r & 1) { update(--r, v); } l >>= 1, r >>= 1; } } }; }; // namespace kyopro /** * @brief Dual Segment Tree */ #line 1 "Library/src/debug.hpp" #ifdef ONLINE_JUDGE #define debug(x) void(0) #else #define _GLIBCXX_DEBUG #define debug(x) std::cerr << __LINE__ << " : " << #x << " = " << (x) << std::endl #endif #line 2 "Library/src/stream.hpp" #include #include #include #line 2 "Library/src/internal/type_traits.hpp" #include #include #include #include #include namespace kyopro { namespace internal { template struct first_enabled {}; template struct first_enabled, Args...> { using type = T; }; template struct first_enabled, Args...> : first_enabled {}; template struct first_enabled { using type = T; }; template using first_enabled_t = typename first_enabled::type; template * = nullptr> struct int_least { using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if>; }; template * = nullptr> struct uint_least { using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if>; }; template using int_least_t = typename int_least::type; template using uint_least_t = typename uint_least::type; template using double_size_uint_t = uint_least_t<2 * std::numeric_limits::digits>; template using double_size_int_t = int_least_t<2 * std::numeric_limits::digits>; struct modint_base {}; template using is_modint = std::is_base_of; template using is_modint_t = std::enable_if_t::value>; // is_integral template using is_integral_t = std::enable_if_t || std::is_same_v || std::is_same_v>; }; // namespace internal }; // namespace kyopro /* * @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8 */ #line 6 "Library/src/stream.hpp" namespace kyopro { inline void single_read(char& c) { c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); } template * = nullptr> inline void single_read(T& a) { a = 0; bool is_negative = false; char c = getchar_unlocked(); while (isspace(c)) { c = getchar_unlocked(); } if (c == '-') is_negative = true, c = getchar_unlocked(); while (isdigit(c)) { a = 10 * a + (c - '0'); c = getchar_unlocked(); } if (is_negative) a *= -1; } template * = nullptr> inline void single_read(T& a) { long long x; single_read(x); a = T(x); } inline void single_read(std::string& str) noexcept { char c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); while (!isspace(c)) { str += c; c = getchar_unlocked(); } } template inline void read(T& x) noexcept {single_read(x);} template inline void read(Head& head, Tail&... tail) noexcept { single_read(head), read(tail...); } inline void single_write(char c) noexcept { putchar_unlocked(c); } template * = nullptr> inline void single_write(T a) noexcept { if (!a) { putchar_unlocked('0'); return; } if constexpr (std::is_signed_v) { if (a < 0) putchar_unlocked('-'), a *= -1; } constexpr int d = std::numeric_limits::digits10; char s[d + 1]; int now = d + 1; while (a) { s[--now] = (char)'0' + a % 10; a /= 10; } while (now <= d) putchar_unlocked(s[now++]); } template * = nullptr> inline void single_write(T a) noexcept { single_write(a.val()); } inline void single_write(const std::string& str) noexcept { for (auto c : str) { putchar_unlocked(c); } } template inline void write(T x) noexcept { single_write(x); } template inline void write(Head head, Tail... tail) noexcept { single_write(head); putchar_unlocked(' '); write(tail...); } template inline void put(Args... x) noexcept { write(x...); putchar_unlocked('\n'); } }; // namespace kyopro /** * @brief 高速入出力 */ #line 2 "Library/src/template.hpp" #include #define rep(i, n) for (int i = 0; i < (n); i++) #define all(x) std::begin(x), std::end(x) #define popcount(x) __builtin_popcountll(x) using i128 = __int128_t; using ll = long long; using ld = long double; using graph = std::vector>; using P = std::pair; constexpr int inf = std::numeric_limits::max() / 2; constexpr ll infl = std::numeric_limits::max() / 2; const long double pi = acosl(-1); constexpr uint64_t MOD = 1e9 + 7; constexpr uint64_t MOD2 = 998244353; constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0}; constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0}; template constexpr inline bool chmax(T1& a, T2 b) { return a < b && (a = b, true); } template constexpr inline bool chmin(T1& a, T2 b) { return a > b && (a = b, true); } #line 6 "a.cpp" using namespace std; using namespace kyopro; constexpr ll op(ll x, ll y) noexcept { return x + y; } constexpr ll e() noexcept { return 0; } int main() { int n, q; read(n, q); vector a(n); rep(i, n) read(a[i]); dual_segtree sg(n); rep(i, n) sg.apply(i, i + 1, a[i]); BIT s(n - 1); rep(i, n - 1) s.add(i, sg[i + 1] != sg[i]); while (q--) { int t, l, r, x; read(t); if (t == 1) { read(l, r, x); --l; sg.apply(l, r, x); if (l && l < n) s.update(l - 1, sg[l - 1] != sg[l]); if (r && r < n) s.update(r - 1, sg[r - 1] != sg[r]); } else { int l, r; read(l, r); --l; put(s.sum(l, r - 1) + 1); } } }