結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー suisen
提出日時 2022-06-19 18:49:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 11,978 bytes
コンパイル時間 941 ms
コンパイル使用メモリ 83,028 KB
最終ジャッジ日時 2025-01-29 23:24:12
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 36 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#define PROBLEM "https://yukicoder.me/problems/no/880"
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <limits>
#include <type_traits>
namespace suisen {
// ! utility
template <typename ...Types>
using constraints_t = std::enable_if_t<std::conjunction_v<Types...>, std::nullptr_t>;
template <bool cond_v, typename Then, typename OrElse>
constexpr decltype(auto) constexpr_if(Then&& then, OrElse&& or_else) {
if constexpr (cond_v) {
return std::forward<Then>(then);
} else {
return std::forward<OrElse>(or_else);
}
}
// ! function
template <typename ReturnType, typename Callable, typename ...Args>
using is_same_as_invoke_result = std::is_same<std::invoke_result_t<Callable, Args...>, ReturnType>;
template <typename F, typename T>
using is_uni_op = is_same_as_invoke_result<T, F, T>;
template <typename F, typename T>
using is_bin_op = is_same_as_invoke_result<T, F, T, T>;
template <typename Comparator, typename T>
using is_comparator = std::is_same<std::invoke_result_t<Comparator, T, T>, bool>;
// ! integral
template <typename T, typename = constraints_t<std::is_integral<T>>>
constexpr int bit_num = std::numeric_limits<std::make_unsigned_t<T>>::digits;
template <typename T, unsigned int n>
struct is_nbit { static constexpr bool value = bit_num<T> == n; };
template <typename T, unsigned int n>
static constexpr bool is_nbit_v = is_nbit<T, n>::value;
// ?
template <typename T>
struct safely_multipliable {};
template <>
struct safely_multipliable<int> { using type = long long; };
template <>
struct safely_multipliable<long long> { using type = __int128_t; };
template <>
struct safely_multipliable<unsigned int> { using type = unsigned long long; };
template <>
struct safely_multipliable<unsigned long int> { using type = __uint128_t; };
template <>
struct safely_multipliable<unsigned long long> { using type = __uint128_t; };
template <>
struct safely_multipliable<float> { using type = float; };
template <>
struct safely_multipliable<double> { using type = double; };
template <>
struct safely_multipliable<long double> { using type = long double; };
template <typename T>
using safely_multipliable_t = typename safely_multipliable<T>::type;
template <typename T, typename = void>
struct rec_value_type {
using type = T;
};
template <typename T>
struct rec_value_type<T, std::void_t<typename T::value_type>> {
using type = typename rec_value_type<typename T::value_type>::type;
};
template <typename T>
using rec_value_type_t = typename rec_value_type<T>::type;
} // namespace suisen
namespace suisen {
template <typename T, typename UpdateFunc, constraints_t<std::is_invocable<UpdateFunc>> = nullptr>
struct UpdateProxyObject {
public:
UpdateProxyObject(T &v, UpdateFunc update) : v(v), update(update) {}
operator T() const { return v; }
auto& operator++() && { ++v, update(); return *this; }
auto& operator--() && { --v, update(); return *this; }
auto& operator+=(const T &val) && { v += val, update(); return *this; }
auto& operator-=(const T &val) && { v -= val, update(); return *this; }
auto& operator*=(const T &val) && { v *= val, update(); return *this; }
auto& operator/=(const T &val) && { v /= val, update(); return *this; }
auto& operator%=(const T &val) && { v %= val, update(); return *this; }
auto& operator =(const T &val) && { v = val, update(); return *this; }
auto& operator<<=(const T &val) && { v <<= val, update(); return *this; }
auto& operator>>=(const T &val) && { v >>= val, update(); return *this; }
template <typename F, constraints_t<is_uni_op<F, T>> = nullptr>
auto& apply(F f) && { v = f(v), update(); return *this; }
private:
T &v;
UpdateFunc update;
};
} // namespace suisen
namespace suisen {
template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)(), bool enable_beats = false>
struct LazySegmentTree {
using value_type = T;
using operator_type = F;
LazySegmentTree() : LazySegmentTree(0) {}
LazySegmentTree(int n) : LazySegmentTree(std::vector<value_type>(n, e())) {}
LazySegmentTree(const std::vector<value_type>& init) : n(init.size()), m(ceil_pow2(n)), lg(__builtin_ctz(m)), data(2 * m, e()), lazy(m, id())
            {
std::copy(init.begin(), init.end(), data.begin() + m);
for (int k = m - 1; k > 0; --k) update(k);
}
void apply(int l, int r, const operator_type& f) {
assert(0 <= l and l <= r and r <= n);
push_to(l, r);
for (int l2 = l + m, r2 = r + m; l2 < r2; l2 >>= 1, r2 >>= 1) {
if (l2 & 1) all_apply(l2++, f);
if (r2 & 1) all_apply(--r2, f);
}
update_from(l, r);
}
void apply(int p, const operator_type& f) {
(*this)[p] = mapping(f, get(p));
}
value_type operator()(int l, int r) {
assert(0 <= l and l <= r and r <= n);
push_to(l, r);
value_type res_l = e(), res_r = e();
for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
if (l & 1) res_l = op(res_l, data[l++]);
if (r & 1) res_r = op(data[--r], res_r);
}
return op(res_l, res_r);
}
value_type prod(int l, int r) { return (*this)(l, r); }
value_type prefix_prod(int r) { return (*this)(0, r); }
value_type suffix_prod(int l) { return (*this)(l, m); }
value_type all_prod() const { return data[1]; }
auto operator[](int p) {
assert(0 <= p and p < n);
push_to(p);
return UpdateProxyObject{ data[p + m], [this, p] { update_from(p); } };
}
value_type get(int p) { return (*this)[p]; }
void set(int p, value_type v) { (*this)[p] = v; }
template <typename Pred, constraints_t<is_same_as_invoke_result<bool, Pred, value_type>> = nullptr>
int max_right(int l, Pred g) {
assert(0 <= l && l <= n);
assert(g(e()));
if (l == n) return n;
l += m;
for (int i = lg; i >= 1; --i) push(l >> i);
value_type sum = e();
do {
while ((l & 1) == 0) l >>= 1;
if (not g(op(sum, data[l]))) {
while (l < m) {
push(l);
l = 2 * l;
if (g(op(sum, data[l]))) sum = op(sum, data[l++]);
}
return l - m;
}
sum = op(sum, data[l++]);
} while ((l & -l) != l);
return n;
}
template <bool(*f)(value_type)>
int max_right(int l) { return max_right(l, f); }
template <typename Pred, constraints_t<is_same_as_invoke_result<bool, Pred, value_type>> = nullptr>
int min_left(int r, Pred g) {
assert(0 <= r && r <= n);
assert(g(e()));
if (r == 0) return 0;
r += m;
for (int i = lg; i >= 1; --i) push(r >> i);
value_type sum = e();
do {
r--;
while (r > 1 and (r & 1)) r >>= 1;
if (not g(op(data[r], sum))) {
while (r < m) {
push(r);
r = 2 * r + 1;
if (g(op(data[r], sum))) sum = op(data[r--], sum);
}
return r + 1 - m;
}
sum = op(data[r], sum);
} while ((r & -r) != r);
return 0;
}
template <bool(*f)(value_type)>
int min_left(int l) { return min_left(l, f); }
private:
int n, m, lg;
std::vector<value_type> data;
std::vector<operator_type> lazy;
static constexpr int ceil_pow2(int n) {
int m = 1;
while (m < n) m <<= 1;
return m;
}
void all_apply(int k, const operator_type& f) {
data[k] = mapping(f, data[k]);
if (k < m) {
lazy[k] = composition(f, lazy[k]);
if constexpr (enable_beats) if (data[k].fail) push(k), update(k);
}
}
void push(int k) {
all_apply(2 * k, lazy[k]), all_apply(2 * k + 1, lazy[k]);
lazy[k] = id();
}
void push_to(int p) {
p += m;
for (int i = lg; i >= 1; --i) push(p >> i);
}
void push_to(int l, int r) {
l += m, r += m;
int li = __builtin_ctz(l), ri = __builtin_ctz(r);
for (int i = lg; i >= li + 1; --i) push(l >> i);
for (int i = lg; i >= ri + 1; --i) push(r >> i);
}
void update(int k) {
data[k] = op(data[2 * k], data[2 * k + 1]);
}
void update_from(int p) {
p += m;
for (int i = 1; i <= lg; ++i) update(p >> i);
}
void update_from(int l, int r) {
l += m, r += m;
int li = __builtin_ctz(l), ri = __builtin_ctz(r);
for (int i = li + 1; i <= lg; ++i) update(l >> i);
for (int i = ri + 1; i <= lg; ++i) update(r >> i);
}
};
}
namespace suisen {
template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
using SegmentTreeBeats = LazySegmentTree<T, op, e, F, mapping, composition, id, /* enable_beats = */ true>;
} // namespace suisen
constexpr long long inf = 2000000000;
struct S {
long long sum_v;
int max_v;
long long lcm_v;
int siz;
bool fail = false;
S(long long sum_v, int max_v, long long lcm_v, int siz) : sum_v(sum_v), max_v(max_v), lcm_v(lcm_v), siz(siz) {}
S(int v) : sum_v(v), max_v(v), lcm_v(v), siz(1) {}
S() = default;
};
struct F {
int upd_v = 0;
int gcd_v = 0;
F(int upd_v = 0, int gcd_v = 0) : upd_v(upd_v), gcd_v(gcd_v) {}
static F upd_query(int upd_v) {
return F { upd_v, 0 };
}
static F gcd_query(int gcd_v) {
return F { 0, gcd_v };
}
};
S op(S x, S y) {
return S { x.sum_v + y.sum_v, std::max(x.max_v, y.max_v), std::min(std::lcm(x.lcm_v, y.lcm_v), inf), x.siz + y.siz };
}
S e() {
return S { 0LL, 0, 1, 0 };
}
S mapping(F f, S x) {
if (f.upd_v) return S { (long long) f.upd_v * x.siz, f.upd_v , f.upd_v, x.siz };
if (f.gcd_v) {
if (x.siz == 1) {
return S { std::gcd(x.max_v, f.gcd_v) };
} else if (f.gcd_v % x.lcm_v) {
x.fail = true;
}
}
return x;
}
F composition(F f, F g) {
if (f.upd_v) return f;
if (g.upd_v) return F::upd_query(std::gcd(g.upd_v, f.gcd_v));
return F::gcd_query(std::gcd(f.gcd_v, g.gcd_v));
}
F id() {
return F::gcd_query(0);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<S> init(n);
for (int i = 0; i < n; ++i) {
int v;
std::cin >> v;
init[i] = S{v};
}
suisen::SegmentTreeBeats<S, op, e, F, mapping, composition, id> seg(init);
while (q --> 0) {
int qt;
std::cin >> qt;
if (qt == 1) {
int l, r, x;
std::cin >> l >> r >> x;
--l;
seg.apply(l, r, F::upd_query(x));
} else if (qt == 2) {
int l, r, x;
std::cin >> l >> r >> x;
--l;
seg.apply(l, r, F::gcd_query(x));
} else if (qt == 3) {
int l, r;
std::cin >> l >> r;
--l;
std::cout << seg.prod(l, r).max_v << '\n';
} else {
int l, r;
std::cin >> l >> r;
--l;
std::cout << seg.prod(l, r).sum_v << '\n';
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0