結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー hashiryohashiryo
提出日時 2022-06-20 19:20:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 442 ms / 5,000 ms
コード長 8,035 bytes
コンパイル時間 2,457 ms
コンパイル使用メモリ 207,912 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2024-09-22 20:01:55
合計ジャッジ時間 12,514 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 413 ms
9,856 KB
testcase_12 AC 396 ms
10,292 KB
testcase_13 AC 284 ms
9,600 KB
testcase_14 AC 396 ms
11,404 KB
testcase_15 AC 416 ms
11,380 KB
testcase_16 AC 442 ms
11,604 KB
testcase_17 AC 325 ms
11,904 KB
testcase_18 AC 325 ms
11,904 KB
testcase_19 AC 260 ms
11,400 KB
testcase_20 AC 264 ms
11,760 KB
testcase_21 AC 270 ms
11,264 KB
testcase_22 AC 270 ms
11,648 KB
testcase_23 AC 278 ms
11,140 KB
testcase_24 AC 228 ms
11,332 KB
testcase_25 AC 239 ms
11,872 KB
testcase_26 AC 250 ms
11,144 KB
testcase_27 AC 231 ms
11,532 KB
testcase_28 AC 246 ms
11,132 KB
testcase_29 AC 389 ms
11,448 KB
testcase_30 AC 405 ms
11,456 KB
testcase_31 AC 433 ms
11,568 KB
testcase_32 AC 120 ms
11,792 KB
testcase_33 AC 212 ms
11,396 KB
testcase_34 AC 230 ms
11,504 KB
testcase_35 AC 217 ms
11,368 KB
testcase_36 AC 221 ms
11,636 KB
testcase_37 AC 216 ms
11,640 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#ifndef TEMP
#define TEMP
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &x) {
  return os << "(" << x.first << ", " << x.second << ")";
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {
  os << '[' << vec[0];
  for (int _ = 1, __ = vec.size(); _ < __; _++) os << ", " << vec[_];
  return os << ']';
}
template <typename T, std::size_t _Nm>
std::ostream &operator<<(std::ostream &os, const std::array<T, _Nm> &arr) {
  os << '[' << arr[0];
  for (std::size_t _ = 1; _ < _Nm; _++) os << ", " << arr[_];
  return os << ']';
}
template <class Tup, std::size_t... I>
void print(std::ostream &os, const Tup &x, std::index_sequence<I...>) {
  using swallow = int[];
  (void)swallow{(os << std::get<I>(x) << ", ", 0)...};
}
template <class... Args>
std::ostream &operator<<(std::ostream &os, const std::tuple<Args...> &x) {
  static constexpr std::size_t N = sizeof...(Args);
  os << "(";
  if constexpr (N >= 2) print(os, x, std::make_index_sequence<N - 1>());
  return os << std::get<N - 1>(x) << ")";
}
#ifdef __LOCAL
const std::string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m",
                  BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m",
                  NORMAL_CROSSED = "\033[0;9;37m", ITALIC = "\033[3m",
                  BOLD = "\033[1m", RED_BACKGROUND = "\033[1;41m",
                  NORMAL_FAINT = "\033[0;2m";
#define func_LINE_FILE                                                 \
  NORMAL_FAINT << " in " << BOLD << __func__ << NORMAL_FAINT << ITALIC \
               << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET
#define checkpoint() \
  std::cerr << BRIGHT_RED << "< check point! >" << func_LINE_FILE << '\n'
#define debug(x)                                                \
  std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) \
            << func_LINE_FILE << '\n'
#define debugArray(x, n)                                             \
  do {                                                               \
    std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = [" << x[0]; \
    for (int _ = 1; _ < (int)(n); ++_) std::cerr << ", " << x[_];    \
    std::cerr << "]" << func_LINE_FILE << '\n';                      \
  } while (0)
#define debugMatrix(x, h, w)                                       \
  do {                                                             \
    std::cerr << BRIGHT_CYAN << #x << "\n" << COLOR_RESET << "= "; \
    for (int _ = 0; (_) < (int)(h); ++_) {                         \
      std::cerr << ((_ ? "   [" : "[["));                          \
      for (int __ = 0; __ < (int)(w); ++__)                        \
        std::cerr << ((__ ? ", " : "")) << x[_][__];               \
      std::cerr << "]" << (_ + 1 == (int)(h) ? "]" : ",\n");       \
    }                                                              \
    std::cerr << func_LINE_FILE << '\n';                           \
  } while (0)
#else
#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif

template <class T>
auto compress(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  return
      [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };
}

struct ClosedSection {
  long long l, r;
  ClosedSection() : l(1), r(0) {}
  ClosedSection(long long l_, long long r_) : l(l_), r(r_) {}
  bool valid() { return l <= r; }
};
template <class Check>  // closed [l,r]
ClosedSection bin_search(const Check &isok, int l, int r) {
  bool res_l = isok(l), res_r = isok(r);
  if (res_l && res_r) return ClosedSection(l, r);
  if (!res_l && !res_r) return ClosedSection();
  int lb, ub;
  for (int x; ub - lb > 1;) (isok(x = (lb + ub) / 2) == res_l ? lb : ub) = x;
  return res_l ? ClosedSection(l, lb) : ClosedSection(ub, r);
}
template <class Check>
ClosedSection bin_search(const Check &isok, ClosedSection cs) {
  return cs.valid() ? bin_search(isok, cs.l, cs.r) : cs;
}
#endif

template <typename M>
struct SegmentTree_Beats {
  using T = typename M::T;
  using E = typename M::E;
  SegmentTree_Beats() {}
  SegmentTree_Beats(int n_)
      : n(n_),
        height(ceil(log2(n))),
        dat(n * 2, M::ti()),
        laz(n * 2, {E(), false}) {}
  SegmentTree_Beats(int n_, T v1) : SegmentTree_Beats(n_) {
    for (int i = n; i--;) dat[i + n] = v1;
    for (int i = n; --i;) update(i);
  }
  SegmentTree_Beats(const std::vector<T> &v) : SegmentTree_Beats(v.size()) {
    for (int i = n; i--;) dat[i + n] = v[i];
    for (int i = n; --i;) update(i);
  }
  void unsafe_set(int k, T x) { dat[k + n] = x; }
  void rebuild() {
    for (int i = n + n; i--;) laz[i].flg = false;
    for (int i = n; --i;) update(i);
  }
  void apply(int a, int b, E x) {
    a += n, b += n;
    for (int i = height; i; i--)
      if (((a >> i) << i) != a) eval(a >> i);
    for (int i = height; i; i--)
      if (((b >> i) << i) != b) eval((b - 1) >> i);
    for (int l = a, r = b; l < r; l >>= 1, r >>= 1) {
      if (l & 1) propagate(l++, x);
      if (r & 1) propagate(--r, x);
    }
    for (int i = 1; a >> i; i++)
      if (((a >> i) << i) != a) update(a >> i);
    for (int i = 1; b >> i; i++)
      if (((b >> i) << i) != b) update((b - 1) >> i);
  }
  void set(int k, T x) {
    int i = height;
    for (k += n; i; i--) eval(k >> i);
    for (dat[k] = x, laz[k].flg = false, i = 1; k >> i; i++) update(k >> i);
  }
  T fold(int a, int b) {  //[a,b)
    a += n, b += n;
    for (int i = height; i; i--)
      if (((a >> i) << i) != a) eval(a >> i);
    for (int i = height; i; i--)
      if (((b >> i) << i) != b) eval(b >> i);
    T vl = M::ti(), vr = M::ti();
    for (int l = a, r = b; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = M::op(vl, dat[l++]);
      if (r & 1) vr = M::op(dat[--r], vr);
    }
    return M::op(vl, vr);
  }
  T operator[](const int k) { return fold(k, k + 1); }

 private:
  const int n, height;
  struct Lazy {
    E val;
    bool flg;
  };
  std::vector<T> dat;
  std::vector<Lazy> laz;
  inline void eval(int k) {
    if (!laz[k].flg) return;
    propagate(k << 1 | 0, laz[k].val), propagate(k << 1 | 1, laz[k].val);
    laz[k].flg = false;
  }
  inline void propagate(int k, const E &x) {
    if (bool success = M::mapping(dat[k], x); k < n) {
      laz[k] = {laz[k].flg ? M::composition(laz[k].val, x) : x, true};
      if (!success) eval(k), update(k);
    }
  }
  inline void update(int k) {
    dat[k] = M::op(dat[k << 1 | 0], dat[k << 1 | 1]);
  }
};

using namespace std;
struct Mono {
  struct T {
    uint64_t max, sum, lcm;
    uint32_t sz;
  };
  static T ti() { return {0, 0, 1, 0}; }
  static T op(const T &vl, const T &vr) {
    return {max(vl.max, vr.max), vl.sum + vr.sum,
            min(1ull * lcm(vl.lcm, vr.lcm), ULLONG_MAX / 10), vl.sz + vr.sz};
  }
  struct E {
    uint32_t upd, gcd;
  };
  static bool mapping(T &v, const E &f) {
    if (f.gcd == 0) return v.sum = (v.lcm = v.max = f.upd) * v.sz, true;
    if (f.gcd % v.lcm == 0) return true;
    if (v.max * v.sz != v.sum) return false;
    return v.sum = (v.lcm = v.max = gcd(v.max, f.gcd)) * v.sz, true;
  }
  static E composition(const E &pre, const E &suf) {
    if (pre.gcd != 0 && suf.gcd != 0) return {0, gcd(pre.gcd, suf.gcd)};
    return {suf.gcd == 0 ? suf.upd : gcd(pre.upd, suf.gcd), 0};
  }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, Q;
  cin >> N >> Q;
  SegmentTree_Beats<Mono> seg(N);
  for (int i = 0; i < N; i++) {
    unsigned a;
    cin >> a;
    seg.unsafe_set(i, {a, a, a, 1});
  }
  seg.rebuild();
  while (Q--) {
    int op, l, r;
    cin >> op >> l >> r, l--;
    if (op < 3) {
      unsigned x;
      cin >> x;
      if (op == 1) seg.apply(l, r, {x, 0});
      if (op == 2) seg.apply(l, r, {0, x});
    } else {
      if (op == 3) cout << seg.fold(l, r).max << '\n';
      if (op == 4) cout << seg.fold(l, r).sum << '\n';
    }
  }
  return 0;
}
0