Submit Info #46933

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp jell AC 2121 ms 15.32 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.61 MiB
max_random_00 AC 1350 ms 15.30 MiB
max_random_01 AC 1356 ms 15.32 MiB
max_random_02 AC 1355 ms 15.32 MiB
medium_00 AC 3 ms 0.68 MiB
medium_01 AC 2 ms 0.64 MiB
medium_02 AC 2 ms 0.62 MiB
random2_00 AC 1790 ms 3.25 MiB
random2_01 AC 1784 ms 3.22 MiB
random2_02 AC 1783 ms 3.27 MiB
random3_00 AC 2115 ms 2.33 MiB
random3_01 AC 2121 ms 2.30 MiB
random3_02 AC 2118 ms 2.30 MiB
random_00 AC 827 ms 10.14 MiB
random_01 AC 892 ms 11.71 MiB
random_02 AC 458 ms 4.80 MiB
small_00 AC 3 ms 0.60 MiB
small_01 AC 1 ms 0.61 MiB
small_02 AC 1 ms 0.68 MiB
small_03 AC 1 ms 0.68 MiB
small_04 AC 1 ms 0.64 MiB
small_05 AC 1 ms 0.70 MiB
small_06 AC 0 ms 0.62 MiB
small_07 AC 1 ms 0.67 MiB
small_08 AC 1 ms 0.60 MiB
small_09 AC 1 ms 0.61 MiB

#line 1 "test/library-checker/range_chmin_chmax_add_range_sum.test.cpp" #define PROBLEM \ "https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum" #include <algorithm> #include <cstdio> #include <map> #line 2 "src/data_structure/buckets.hpp" /** * @file buckets.hpp * @brief Buckets */ #include <cmath> #include <vector> namespace workspace { /** * @brief Buckets on a sequence. */ template <class _Iterator, class _Pack, class _Unpack> struct buckets { static_assert( std::is_same<typename std::iterator_traits<_Iterator>::iterator_category, std::random_access_iterator_tag>::value); using difference_type = typename std::iterator_traits<_Iterator>::difference_type; _Iterator __begin, __end; using value_type = decltype(std::declval<_Pack>()(std::declval<_Iterator>(), std::declval<_Iterator>())); struct bucket { value_type __data; _Iterator __begin; _Iterator __end; }; _Pack __pack; _Unpack __unpack; difference_type __unit; std::vector<bucket> __buckets; void prepare() { if (!__unit) __unit = round(sqrt(std::distance(__begin, __end))); for (auto __l = __begin, __r = __l; __r != __end; __l = __r) { for (auto __n = __unit; __r != __end && __n; --__n) ++__r; __buckets.push_back({__pack(__l, __r), __l, __r}); } } public: /** * @brief Constuct a new buckets object. */ buckets(_Iterator __first, _Iterator __last, _Pack __pack, _Unpack __unpack, difference_type __unit = 0) : __begin(__first), __end(__last), __pack(__pack), __unpack(__unpack), __unit(__unit) { prepare(); } /** * @brief Number of buckets. */ auto size() const { return __buckets.size(); } bool empty() const { return __begin == __end; } /** * @brief Operate on a subsegment. * * @param __first * @param __last * @param __oper */ template <class _Operator> void operator()(_Iterator __first, _Iterator __last, _Operator __oper) { if (__first == __last) return; auto __index = std::distance(__begin, __first); auto __b = std::next(__buckets.begin(), __index / __unit); if (__index % __unit) { __unpack(__b->__data, __b->__begin, __b->__end); auto __mid = std::distance(__last, __b->__end) > 0 ? __last : __b->__end; auto __tmp = __pack(__first, __mid); __oper(__tmp); __unpack(__tmp, __first, __mid); __b->__data = __pack(__b->__begin, __b->__end); ++__b; } while (true) { if (__b == __buckets.end()) return; if (std::distance(__b->__end, __last) < 0) break; __oper(__b->__data); ++__b; } if (std::distance(__b->__begin, __last) > 0) { __unpack(__b->__data, __b->__begin, __b->__end); auto __tmp = __pack(__b->__begin, __last); __oper(__tmp); __unpack(__tmp, __b->__begin, __last); __b->__data = __pack(__b->__begin, __b->__end); } } /** * @brief Operate on a subsegment. * * @param __i * @param __j * @param __oper */ template <class _Operator> void operator()(difference_type __i, difference_type __j, _Operator __oper) { operator()(std::next(__begin, __i), std::next(__begin, __j), __oper); } }; } // namespace workspace #line 2 "src/modular/modint.hpp" /** * @file modint.hpp * * @brief Modular Arithmetic */ #include <cassert> #include <iostream> #line 12 "src/modular/modint.hpp" #line 2 "src/number_theory/sqrt_mod.hpp" /** * @file sqrt_mod.hpp * @brief Tonelli-Shanks Algorithm */ #line 2 "src/number_theory/pow_mod.hpp" /** * @file mod_pow.hpp * @brief Modular Exponentiation */ #line 9 "src/number_theory/pow_mod.hpp" #line 2 "src/utils/sfinae.hpp" /** * @file sfinae.hpp * @brief SFINAE */ #include <cstdint> #include <iterator> #include <type_traits> #ifndef __INT128_DEFINED__ #ifdef __SIZEOF_INT128__ #define __INT128_DEFINED__ 1 #else #define __INT128_DEFINED__ 0 #endif #endif namespace std { #if __INT128_DEFINED__ template <> struct make_signed<__uint128_t> { using type = __int128_t; }; template <> struct make_signed<__int128_t> { using type = __int128_t; }; template <> struct make_unsigned<__uint128_t> { using type = __uint128_t; }; template <> struct make_unsigned<__int128_t> { using type = __uint128_t; }; template <> struct is_signed<__uint128_t> : std::false_type {}; template <> struct is_signed<__int128_t> : std::true_type {}; template <> struct is_unsigned<__uint128_t> : std::true_type {}; template <> struct is_unsigned<__int128_t> : std::false_type {}; #endif } // namespace std namespace workspace { template <class Tp, class... Args> struct variadic_front { using type = Tp; }; template <class... Args> struct variadic_back; template <class Tp> struct variadic_back<Tp> { using type = Tp; }; template <class Tp, class... Args> struct variadic_back<Tp, Args...> { using type = typename variadic_back<Args...>::type; }; template <class type, template <class> class trait> using enable_if_trait_type = typename std::enable_if<trait<type>::value>::type; /** * @brief Return type of subscripting ( @c [] ) access. */ template <class _Tp> using subscripted_type = typename std::decay<decltype(std::declval<_Tp&>()[0])>::type; template <class Container> using element_type = typename std::decay<decltype( *std::begin(std::declval<Container&>()))>::type; template <class _Tp, class = std::nullptr_t> struct has_begin : std::false_type {}; template <class _Tp> struct has_begin<_Tp, decltype(std::begin(std::declval<_Tp>()), nullptr)> : std::true_type {}; template <class _Tp, class = std::nullptr_t> struct has_mod : std::false_type {}; template <class _Tp> struct has_mod<_Tp, decltype(_Tp::mod, nullptr)> : std::true_type {}; template <class _Tp, class = void> struct is_integral_ext : std::false_type {}; template <class _Tp> struct is_integral_ext< _Tp, typename std::enable_if<std::is_integral<_Tp>::value>::type> : std::true_type {}; #if __INT128_DEFINED__ template <> struct is_integral_ext<__int128_t> : std::true_type {}; template <> struct is_integral_ext<__uint128_t> : std::true_type {}; #endif #if __cplusplus >= 201402 template <class _Tp> constexpr static bool is_integral_ext_v = is_integral_ext<_Tp>::value; #endif template <typename _Tp, typename = void> struct multiplicable_uint { using type = uint_least32_t; }; template <typename _Tp> struct multiplicable_uint< _Tp, typename std::enable_if<(2 < sizeof(_Tp)) && (!__INT128_DEFINED__ || sizeof(_Tp) <= 4)>::type> { using type = uint_least64_t; }; #if __INT128_DEFINED__ template <typename _Tp> struct multiplicable_uint<_Tp, typename std::enable_if<(4 < sizeof(_Tp))>::type> { using type = __uint128_t; }; #endif template <typename _Tp> struct multiplicable_int { using type = typename std::make_signed<typename multiplicable_uint<_Tp>::type>::type; }; template <typename _Tp> struct multiplicable { using type = std::conditional_t< is_integral_ext<_Tp>::value, std::conditional_t<std::is_signed<_Tp>::value, typename multiplicable_int<_Tp>::type, typename multiplicable_uint<_Tp>::type>, _Tp>; }; } // namespace workspace #line 11 "src/number_theory/pow_mod.hpp" namespace workspace { /** * @brief Compile time modular exponentiation. * * @param __x * @param __n Exponent * @param __mod Modulus * @return */ template <class _Tp> constexpr std::enable_if_t<(is_integral_ext<_Tp>::value), _Tp> pow_mod( _Tp __x, _Tp __n, _Tp __mod) noexcept { assert(__mod > 0); using mul_type = typename multiplicable_uint<_Tp>::type; if ((__x %= __mod) < 0) __x += __mod; mul_type __y{1}; while (__n) { if (__n & 1) (__y *= __x) %= __mod; __x = (mul_type)__x * __x % __mod; __n >>= 1; } return __y; }; } // namespace workspace #line 10 "src/number_theory/sqrt_mod.hpp" namespace workspace { /** * @brief Compile time modular square root. * * @param __x * @param __mod Modulus * @return One if it exists. Otherwise -1. */ template <class _Tp> constexpr std::enable_if_t<(is_integral_ext<_Tp>::value), _Tp> sqrt_mod( _Tp __x, _Tp __mod) noexcept { assert(__mod > 0); using mul_type = typename multiplicable_uint<_Tp>::type; if ((__x %= __mod) < 0) __x += __mod; if (!__x) return 0; if (__mod == 2) return __x; if (pow_mod(__x, __mod >> 1, __mod) != 1) return -1; _Tp __z = __builtin_ctz(__mod - 1), __q = __mod >> __z; mul_type __a = pow_mod(__x, (__q + 1) >> 1, __mod), __b = 2; while (pow_mod<_Tp>(__b, __mod >> 1, __mod) == 1) ++__b; __b = pow_mod<_Tp>(__b, __q, __mod); _Tp __shift = 0; for (auto __r = __a * __a % __mod * pow_mod(__x, __mod - 2, __mod) % __mod; __r != 1; (__r *= (__b *= __b) %= __mod) %= __mod) { auto __bsf = __z; for (auto __e = __r; __e != 1; --__bsf) (__e *= __e) %= __mod; while (++__shift != __bsf) (__b *= __b) %= __mod; (__a *= __b) %= __mod; } return __a; }; } // namespace workspace #line 15 "src/modular/modint.hpp" namespace workspace { namespace _modint_impl { template <auto _Mod, unsigned _Storage> struct modint { static_assert(is_integral_ext<decltype(_Mod)>::value, "_Mod must be integral type."); using mod_type = std::make_signed_t<typename std::conditional< 0 < _Mod, std::add_const_t<decltype(_Mod)>, decltype(_Mod)>::type>; using value_type = std::decay_t<mod_type>; using mul_type = typename multiplicable_uint<value_type>::type; // Modulus static mod_type mod; static unsigned storage; private: value_type value = 0; struct direct_ctor_t {}; constexpr static direct_ctor_t direct_ctor_tag{}; // Direct constructor template <class _Tp> constexpr modint(_Tp __n, direct_ctor_t) noexcept : value(__n) {} public: constexpr modint() noexcept = default; template <class _Tp, typename = std::enable_if_t<is_integral_ext<_Tp>::value>> constexpr modint(_Tp __n) noexcept : value((__n %= mod) < 0 ? __n += mod : __n) {} constexpr modint(bool __n) noexcept : value(__n) {} constexpr operator value_type() const noexcept { return value; } // unary operators {{ constexpr modint operator++(int) noexcept { modint __t{*this}; operator++(); return __t; } constexpr modint operator--(int) noexcept { modint __t{*this}; operator--(); return __t; } constexpr modint &operator++() noexcept { if (++value == mod) value = 0; return *this; } constexpr modint &operator--() noexcept { if (!value) value = mod - 1; else --value; return *this; } constexpr modint operator+() const noexcept { return *this; } constexpr modint operator-() const noexcept { return {value ? mod - value : 0, direct_ctor_tag}; } // }} unary operators // operator+= {{ constexpr modint &operator+=(const modint &__x) noexcept { if ((value += __x.value) >= mod) value -= mod; return *this; } template <class _Tp> constexpr std::enable_if_t<is_integral_ext<_Tp>::value, modint> &operator+=( _Tp const &__x) noexcept { if (((value += __x) %= mod) < 0) value += mod; return *this; } // }} operator+= // operator+ {{ template <class _Tp> constexpr std::enable_if_t<is_integral_ext<_Tp>::value, modint> operator+( _Tp const &__x) const noexcept { return modint{*this} += __x; } constexpr modint operator+(modint __x) const noexcept { return __x += *this; } template <class _Tp> constexpr friend std::enable_if_t<is_integral_ext<_Tp>::value, modint> operator+(_Tp const &__x, modint __y) noexcept { return __y += __x; } // }} operator+ // operator-= {{ constexpr modint &operator-=(const modint &__x) noexcept { if ((value -= __x.value) < 0) value += mod; return *this; } template <class _Tp> constexpr std::enable_if_t<is_integral_ext<_Tp>::value, modint> &operator-=( _Tp __x) noexcept { if (((value -= __x) %= mod) < 0) value += mod; return *this; } // }} operator-= // operator- {{ template <class _Tp> constexpr std::enable_if_t<is_integral_ext<_Tp>::value, modint> operator-( _Tp const &__x) const noexcept { return modint{*this} -= __x; } constexpr modint operator-(const modint &__x) const noexcept { return modint{*this} -= __x; } template <class _Tp> constexpr friend std::enable_if_t<is_integral_ext<_Tp>::value, modint> operator-(_Tp __x, const modint &__y) noexcept { if (((__x -= __y.value) %= mod) < 0) __x += mod; return {__x, direct_ctor_tag}; } // }} operator- // operator*= {{ constexpr modint &operator*=(const modint &__x) noexcept { value = static_cast<value_type>(value * static_cast<mul_type>(__x.value) % mod); return *this; } template <class _Tp> constexpr std::enable_if_t<is_integral_ext<_Tp>::value, modint> &operator*=( _Tp __x) noexcept { value = static_cast<value_type>( value * mul_type((__x %= mod) < 0 ? __x + mod : __x) % mod); return *this; } // }} operator*= // operator* {{ constexpr modint operator*(const modint &__x) const noexcept { return {static_cast<mul_type>(value) * __x.value % mod, direct_ctor_tag}; } template <class _Tp> constexpr std::enable_if_t<is_integral_ext<_Tp>::value, modint> operator*( _Tp __x) const noexcept { __x %= mod; if (__x < 0) __x += mod; return {static_cast<mul_type>(value) * __x % mod, direct_ctor_tag}; } template <class _Tp> constexpr friend std::enable_if_t<is_integral_ext<_Tp>::value, modint> operator*(_Tp __x, const modint &__y) noexcept { __x %= mod; if (__x < 0) __x += mod; return {static_cast<mul_type>(__x) * __y.value % mod, direct_ctor_tag}; } // }} operator* protected: static value_type _mem(value_type __x) { static std::vector<value_type> __m{0, 1}; static value_type __i = (__m.reserve(storage), 1); while (__i < __x) { ++__i; __m.emplace_back(mod - mul_type(mod / __i) * __m[mod % __i] % mod); } return __m[__x]; } static value_type _div(mul_type __r, value_type __x) noexcept { assert(__x != value_type(0)); if (!__r) return 0; std::make_signed_t<value_type> __v{}; bool __neg = __x < 0 ? __x = -__x, true : false; if (static_cast<decltype(storage)>(__x) < storage) __v = _mem(__x); else { value_type __y{mod}, __u{1}, __t; while (__x) __t = __y / __x, __y ^= __x ^= (__y -= __t * __x) ^= __x, __v ^= __u ^= (__v -= __t * __u) ^= __u; if (__y < 0) __neg ^= 1; } if (__neg) __v = 0 < __v ? mod - __v : -__v; else if (__v < 0) __v += mod; return __r == mul_type(1) ? static_cast<value_type>(__v) : static_cast<value_type>(__r * __v % mod); } public: // operator/= {{ constexpr modint &operator/=(const modint &__x) noexcept { if (value) value = _div(value, __x.value); return *this; } template <class _Tp> constexpr std::enable_if_t<is_integral_ext<_Tp>::value, modint> &operator/=( _Tp __x) noexcept { if (value) value = _div(value, __x %= mod); return *this; } // }} operator/= // operator/ {{ constexpr modint operator/(const modint &__x) const noexcept { if (!value) return {}; return {_div(value, __x.value), direct_ctor_tag}; } template <class _Tp> constexpr std::enable_if_t<is_integral_ext<_Tp>::value, modint> operator/( _Tp __x) const noexcept { if (!value) return {}; return {_div(value, __x %= mod), direct_ctor_tag}; } template <class _Tp> constexpr friend std::enable_if_t<is_integral_ext<_Tp>::value, modint> operator/(_Tp __x, const modint &__y) noexcept { if (!__x) return {}; if ((__x %= mod) < 0) __x += mod; return {_div(__x, __y.value), direct_ctor_tag}; } // }} operator/ constexpr modint inv() const noexcept { return _div(1, value); } template <class _Tp> constexpr std::enable_if_t<is_integral_ext<_Tp>::value, modint> pow( _Tp __e) const noexcept { modint __r{1, direct_ctor_tag}; for (modint __b{__e < 0 ? __e = -__e, _div(1, value) : value, direct_ctor_tag}; __e; __e >>= 1, __b *= __b) if (__e & 1) __r *= __b; return __r; } template <class _Tp> constexpr friend std::enable_if_t<is_integral_ext<_Tp>::value, modint> pow( modint __b, _Tp __e) noexcept { if (__e < 0) { __e = -__e; __b.value = _div(1, __b.value); } modint __r{1, direct_ctor_tag}; for (; __e; __e >>= 1, __b *= __b) if (__e & 1) __r *= __b; return __r; } constexpr modint sqrt() const noexcept { return {sqrt_mod(value, mod), direct_ctor_tag}; } friend constexpr modint sqrt(const modint &__x) noexcept { return {sqrt_mod(__x.value, mod), direct_ctor_tag}; } template <class _Os> friend _Os &operator<<(_Os &__os, const modint &__x) noexcept { return __os << __x.value; } friend std::istream &operator>>(std::istream &__is, modint &__x) noexcept { std::string __s; __is >> __s; bool __neg = false; if (__s.front() == '-') { __neg = true; __s.erase(__s.begin()); } __x = 0; for (char __c : __s) __x = __x * 10 + (__c - '0'); if (__neg) __x = -__x; return __is; } }; template <auto _Mod, unsigned _Storage> typename modint<_Mod, _Storage>::mod_type modint<_Mod, _Storage>::mod = _Mod > 0 ? _Mod : 0; template <auto _Mod, unsigned _Storage> unsigned modint<_Mod, _Storage>::storage = _Storage; } // namespace _modint_impl template <auto _Mod, unsigned _Storage = 0, typename = std::enable_if_t<(_Mod > 0)>> using modint = _modint_impl::modint<_Mod, _Storage>; template <unsigned _Id = 0> using modint_runtime = _modint_impl::modint<-(signed)_Id, 0>; } // namespace workspace #line 10 "test/library-checker/range_chmin_chmax_add_range_sum.test.cpp" int main() { using namespace workspace; using i64 = int_least64_t; int n, q; scanf("%d%d", &n, &q); std::vector<i64> a(n); for (auto&& x : a) { scanf("%lld", &x); } struct data { i64 min, max, add, sum, num; std::map<i64, i64> map; }; constexpr auto inf = 1'000'000'000'000; buckets b( begin(a), end(a), [](auto l, auto r) { data d; d.add = 0; d.sum = 0; d.min = inf; d.max = -inf; d.num = 0; while (l != r) { d.sum += *l; d.map[*l] += 1; d.num += 1; ++l; } return d; }, [](const auto& d, auto l, auto r) { while (l != r) { *l = std::min(d.min, std::max(d.max, *l)) + d.add; ++l; } }); for (int t, l, r; q--;) { scanf("%d%d%d", &t, &l, &r); if (t == 3) { i64 sum = 0; b(l, r, [&](const auto& x) { sum += x.sum; }); printf("%lld\n", sum); continue; } i64 a; scanf("%lld", &a); switch (t) { case 0: b(l, r, [&](auto& d) { auto c = a - d.add; if (d.min < c) return; d.min = c; if (d.max > c) d.max = c; while (d.map.rbegin()->first > c) { auto [v, k] = *prev(d.map.end()); d.map.erase(prev(d.map.end())); d.map[c] += k; d.sum += (c - v) * k; } }); break; case 1: b(l, r, [&](auto& d) { auto c = a - d.add; if (d.max > c) return; d.max = c; if (d.min < c) d.min = c; while (d.map.begin()->first < c) { auto [v, k] = *d.map.begin(); d.map.erase(d.map.begin()); d.map[c] += k; d.sum += (c - v) * k; } }); break; case 2: b(l, r, [&](auto& x) { x.sum += x.num * a; x.add += a; }); break; } } }