結果

問題 No.876 Range Compress Query
ユーザー AC2KAC2K
提出日時 2024-01-25 11:20:39
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 9,448 bytes
コンパイル時間 2,957 ms
コンパイル使用メモリ 253,040 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-28 07:17:39
合計ジャッジ時間 4,419 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 48 ms
6,940 KB
testcase_12 AC 40 ms
6,940 KB
testcase_13 AC 41 ms
6,940 KB
testcase_14 AC 46 ms
6,940 KB
testcase_15 AC 38 ms
6,944 KB
testcase_16 AC 49 ms
6,940 KB
testcase_17 AC 48 ms
6,940 KB
testcase_18 AC 51 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "Library/src/data-structure/BIT.hpp"
#include <vector>
namespace kyopro {

template <typename T> class BIT {
    std::vector<T> 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 <cassert>
#line 4 "Library/src/data-structure/dual_segtree.hpp"
namespace kyopro {
template <class F, auto composition, auto id> class dual_segtree {
    std::vector<F> 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 <ctype.h>
#include <stdio.h>
#include <string>
#line 2 "Library/src/internal/type_traits.hpp"
#include <iostream>
#include <limits>
#include <numeric>
#include <typeinfo>
#include <cstdint>

namespace kyopro {
namespace internal {
template <typename... Args> struct first_enabled {};

template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
    using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
    : first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
    using type = T;
};

template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;

template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least {
    using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>,
                                 std::enable_if<dgt <= 16, std::int16_t>,
                                 std::enable_if<dgt <= 32, std::int32_t>,
                                 std::enable_if<dgt <= 64, std::int64_t>,
                                 std::enable_if<dgt <= 128, __int128_t>>;
};

template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least {
    using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>,
                                 std::enable_if<dgt <= 16, std::uint16_t>,
                                 std::enable_if<dgt <= 32, std::uint32_t>,
                                 std::enable_if<dgt <= 64, std::uint64_t>,
                                 std::enable_if<dgt <= 128, __uint128_t>>;
};

template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;

template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;

template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;

struct modint_base {};
template <typename T> using is_modint = std::is_base_of<modint_base, T>;
template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;


// is_integral
template <typename T>
using is_integral_t =
    std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||
                   std::is_same_v<T, __uint128_t>>;
};  // 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 <typename T, internal::is_integral_t<T>* = 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 <typename T, internal::is_modint_t<T>* = 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<typename T>
inline void read(T& x) noexcept {single_read(x);}
template <typename Head, typename... Tail>
inline void read(Head& head, Tail&... tail) noexcept {
    single_read(head), read(tail...);
}

inline void single_write(char c) noexcept { putchar_unlocked(c); }
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_write(T a) noexcept {
    if (!a) {
        putchar_unlocked('0');
        return;
    }
    if constexpr (std::is_signed_v<T>) {
        if (a < 0) putchar_unlocked('-'), a *= -1;
    }
    constexpr int d = std::numeric_limits<T>::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 <typename T, internal::is_modint_t<T>* = 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 <typename T> inline void write(T x) noexcept { single_write(x); }
template <typename Head, typename... Tail>
inline void write(Head head, Tail... tail) noexcept {
    single_write(head);
    putchar_unlocked(' ');
    write(tail...);
}
template <typename... Args> inline void put(Args... x) noexcept {
    write(x...);
    putchar_unlocked('\n');
}
};  // namespace kyopro

/**
 * @brief 高速入出力
 */
#line 2 "Library/src/template.hpp"
#include <bits/stdc++.h>
#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<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infl = std::numeric_limits<ll>::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 <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> 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<int> a(n);
    rep(i, n) read(a[i]);
    dual_segtree<int, op, e> sg(n);
    rep(i, n) sg.apply(i, i + 1, a[i]);
    BIT<int> 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);
        }
    }
}
0