結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー kusaf_kusaf_
提出日時 2024-12-24 01:22:48
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 599 ms / 5,000 ms
コード長 5,683 bytes
コンパイル時間 3,099 ms
コンパイル使用メモリ 257,540 KB
実行使用メモリ 19,456 KB
最終ジャッジ日時 2024-12-24 01:23:08
合計ジャッジ時間 15,685 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 4 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 3 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 4 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 470 ms
18,560 KB
testcase_12 AC 419 ms
18,724 KB
testcase_13 AC 301 ms
18,432 KB
testcase_14 AC 436 ms
19,168 KB
testcase_15 AC 432 ms
19,200 KB
testcase_16 AC 453 ms
19,316 KB
testcase_17 AC 396 ms
19,408 KB
testcase_18 AC 381 ms
19,456 KB
testcase_19 AC 310 ms
19,200 KB
testcase_20 AC 342 ms
19,456 KB
testcase_21 AC 330 ms
19,072 KB
testcase_22 AC 305 ms
19,312 KB
testcase_23 AC 335 ms
19,200 KB
testcase_24 AC 350 ms
19,204 KB
testcase_25 AC 284 ms
19,408 KB
testcase_26 AC 297 ms
19,072 KB
testcase_27 AC 283 ms
19,140 KB
testcase_28 AC 293 ms
19,256 KB
testcase_29 AC 410 ms
19,200 KB
testcase_30 AC 524 ms
19,220 KB
testcase_31 AC 599 ms
19,328 KB
testcase_32 AC 142 ms
19,328 KB
testcase_33 AC 370 ms
19,196 KB
testcase_34 AC 395 ms
19,324 KB
testcase_35 AC 397 ms
19,200 KB
testcase_36 AC 356 ms
19,328 KB
testcase_37 AC 321 ms
19,328 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 {
 public:
  lazy_segtree(): lazy_segtree(0) {}
  explicit lazy_segtree(int n): lazy_segtree(vector<S>(n, e())) {}
  explicit lazy_segtree(const vector<S> &v): _n(int(v.size())) {
    size = (int)bit_ceil((unsigned int)(_n));
    log = countr_zero((unsigned int)size);
    d = vector<S>(2 * size, e());
    lz = 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;
  vector<S> d;
  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