結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー kusaf_kusaf_
提出日時 2024-02-24 00:49:27
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 498 ms / 5,000 ms
コード長 6,250 bytes
コンパイル時間 3,142 ms
コンパイル使用メモリ 257,736 KB
実行使用メモリ 19,452 KB
最終ジャッジ日時 2024-09-29 09:37:30
合計ジャッジ時間 15,308 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 3 ms
6,820 KB
testcase_02 AC 4 ms
6,816 KB
testcase_03 AC 3 ms
6,820 KB
testcase_04 AC 3 ms
6,820 KB
testcase_05 AC 3 ms
6,816 KB
testcase_06 AC 3 ms
6,816 KB
testcase_07 AC 4 ms
6,820 KB
testcase_08 AC 4 ms
6,820 KB
testcase_09 AC 4 ms
6,816 KB
testcase_10 AC 4 ms
6,820 KB
testcase_11 AC 481 ms
18,584 KB
testcase_12 AC 460 ms
18,728 KB
testcase_13 AC 323 ms
18,332 KB
testcase_14 AC 444 ms
19,280 KB
testcase_15 AC 471 ms
19,140 KB
testcase_16 AC 498 ms
19,264 KB
testcase_17 AC 405 ms
19,256 KB
testcase_18 AC 405 ms
19,416 KB
testcase_19 AC 338 ms
19,204 KB
testcase_20 AC 340 ms
19,452 KB
testcase_21 AC 365 ms
19,104 KB
testcase_22 AC 333 ms
19,260 KB
testcase_23 AC 356 ms
19,292 KB
testcase_24 AC 310 ms
19,180 KB
testcase_25 AC 316 ms
19,344 KB
testcase_26 AC 322 ms
19,092 KB
testcase_27 AC 307 ms
19,280 KB
testcase_28 AC 320 ms
19,160 KB
testcase_29 AC 440 ms
19,192 KB
testcase_30 AC 456 ms
19,192 KB
testcase_31 AC 490 ms
19,264 KB
testcase_32 AC 128 ms
19,404 KB
testcase_33 AC 307 ms
19,256 KB
testcase_34 AC 331 ms
19,260 KB
testcase_35 AC 329 ms
19,192 KB
testcase_36 AC 320 ms
19,300 KB
testcase_37 AC 309 ms
19,336 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<class S, auto op, auto e, class F, auto mapping, auto composition, auto id> struct lazy_segtree {
  static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>, "op must work as S(S, S)");
  static_assert(std::is_convertible_v<decltype(e), std::function<S()>>, "e must work as S()");
  static_assert(std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>, "mapping must work as F(F, S)");
  static_assert(std::is_convertible_v<decltype(composition), std::function<F(F, F)>>, "compostiion must work as F(F, F)");
  static_assert(std::is_convertible_v<decltype(id), std::function<F()>>, "id must work as F()");

 public:
  lazy_segtree(): lazy_segtree(0) {}
  explicit lazy_segtree(int n): lazy_segtree(std::vector<S>(n, e())) {}
  explicit lazy_segtree(const std::vector<S>& v): _n(int(v.size())) {
    size = (int)bit_ceil((unsigned int)(_n));
    log = countr_zero((unsigned int)size);
    d = std::vector<S>(2 * size, e());
    lz = std::vector<F>(size, id());
    for(int i = 0; i < _n; i++) { d[size + i] = v[i]; }
    for(int i = size - 1; i >= 1; i--) { update(i); }
  }
  void set(int p, S x) {
    assert(0 <= p && p < _n);
    p += size;
    for(int i = log; i >= 1; i--) { push(p >> i); }
    d[p] = x;
    for(int i = 1; i <= log; i++) { update(p >> i); }
  }
  S get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for(int i = log; i >= 1; i--) { push(p >> i); }
    return d[p];
  }
  S prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    if(l == r) { return e(); }
    l += size;
    r += size;
    for(int i = log; i >= 1; i--) {
      if(((l >> i) << i) != l) { push(l >> i); }
      if(((r >> i) << i) != r) { push((r - 1) >> i); }
    }
    S sml = e(), smr = e();
    while(l < r) {
      if(l & 1) { sml = op(sml, d[l++]); }
      if(r & 1) { smr = op(d[--r], smr); }
      l >>= 1;
      r >>= 1;
    }
    return op(sml, smr);
  }
  S all_prod() { return d[1]; }
  void apply(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for(int i = log; i >= 1; i--) { push(p >> i); }
    d[p] = mapping(f, d[p]);
    for(int i = 1; i <= log; i++) { update(p >> i); }
  }
  void apply(int l, int r, F f) {
    assert(0 <= l && l <= r && r <= _n);
    if(l == r) return;
    l += size;
    r += size;
    for(int i = log; i >= 1; i--) {
      if(((l >> i) << i) != l) { push(l >> i); }
      if(((r >> i) << i) != r) { push((r - 1) >> i); }
    }
    {
      int l2 = l, r2 = r;
      while(l < r) {
        if(l & 1) { all_apply(l++, f); }
        if(r & 1) { all_apply(--r, f); }
        l >>= 1;
        r >>= 1;
      }
      l = l2;
      r = r2;
    }
    for(int i = 1; i <= log; i++) {
      if(((l >> i) << i) != l) { update(l >> i); }
      if(((r >> i) << i) != r) { update((r - 1) >> i); }
    }
  }
  template<bool (*g)(S)> int max_right(int l) {
    return max_right(l, [](S x) { return g(x); });
  }
  template<class G> int max_right(int l, G g) {
    assert(0 <= l && l <= _n);
    assert(g(e()));
    if(l == _n) { return _n; }
    l += size;
    for(int i = log; i >= 1; i--) { push(l >> i); }
    S sm = e();
    do {
      while(l % 2 == 0) l >>= 1;
      if(!g(op(sm, d[l]))) {
        while(l < size) {
          push(l);
          l = (2 * l);
          if(g(op(sm, d[l]))) {
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - size;
      }
      sm = op(sm, d[l]);
      l++;
    } while((l & -l) != l);
    return _n;
  }
  template<bool (*g)(S)> int min_left(int r) {
    return min_left(r, [](S x) { return g(x); });
  }
  template<class G> int min_left(int r, G g) {
    assert(0 <= r && r <= _n);
    assert(g(e()));
    if(r == 0) { return 0; }
    r += size;
    for(int i = log; i >= 1; i--) { push((r - 1) >> i); }
    S sm = e();
    do {
      r--;
      while(r > 1 && (r % 2)) r >>= 1;
      if(!g(op(d[r], sm))) {
        while(r < size) {
          push(r);
          r = (2 * r + 1);
          if(g(op(d[r], sm))) {
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - size;
      }
      sm = op(d[r], sm);
    } while((r & -r) != r);
    return 0;
  }

 private:
  int _n, size, log;
  std::vector<S> d;
  std::vector<F> lz;
  void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
  void all_apply(int k, F f) {
    d[k] = mapping(f, d[k]);
    if(k < size) {
      lz[k] = composition(f, lz[k]);
      if(d[k].fail) { push(k), update(k); }
    }
  }
  void push(int k) {
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = id();
  }
};

constexpr ll INF = 2e9;
struct S {
  ll max, lcm, sz, sum;
  bool fail;
  S(): max(0), lcm(1), sz(0), sum(0), fail(false) {}
  S(ll x, ll sz = 1): max(x), lcm(x), sz(sz), sum(x * sz), fail(false) {}
};
struct F {
  ll g, upd;
  F(): g(0), upd(0) {}
  F(ll g, ll upd): g(g), upd(upd) {}
  static F gcd(ll x) noexcept { return F(x, 0); }
  static F update(ll x) noexcept { return F(0, x); }
};
S op(S l, S r) {
  if(!r.sz) { return l; }
  if(!l.sz) { return r; }
  S ret;
  ret.max = std::max(l.max, r.max);
  ret.sum = l.sum + r.sum;
  ret.lcm = min(INF, std::lcm(l.lcm, r.lcm));
  ret.sz = l.sz + r.sz;
  return ret;
}
S e() { return S(); }
S fx(F f, S x) {
  if(x.fail) { return x; }
  if(f.upd) { x = S(f.upd, x.sz); }
  if(f.g) {
    if(x.sz * x.max == x.sum) { x = S(gcd(x.max, f.g), x.sz); }
    else if(x.lcm == INF || f.g % x.lcm) { x.fail = true; }
  }
  return x;
}
F fg(F f, F g) {
  if(f.upd) { return F::update(f.upd); }
  else if(g.upd) { return F::update(gcd(f.g, g.upd)); }
  else { return F::gcd(gcd(f.g, g.g)); }
}
F id() { return F(); }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll N, Q;
  cin >> N >> Q;

  vector<S> A(N);
  for(ll i = 0; i < N; i++) {
    ll a;
    cin >> a;
    A[i] = S(a);
  }

  lazy_segtree<S, op, e, F, fx, fg, id> seg(A);

  while(Q--) {
    ll type, l, r, x;
    cin >> type >> l >> r;
    l--;
    if(type <= 2) { cin >> x; }
    if(type == 1) { seg.apply(l, r, F::update(x)); }
    if(type == 2) { seg.apply(l, r, F::gcd(x)); }
    if(type == 3) { cout << seg.prod(l, r).max << "\n"; }
    if(type == 4) { cout << seg.prod(l, r).sum << "\n"; }
  }
}
0