#954754 (C++23) No.880 Yet Another Segment Tree Problem

提出ソース

結果

問題	No.880 Yet Another Segment Tree Problem
ユーザー	kusaf_
提出日時	2024-02-23 23:26:33
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	618 ms / 5,000 ms
コード長	7,482 bytes
コンパイル時間	3,232 ms
コンパイル使用メモリ	261,060 KB
実行使用メモリ	15,616 KB
最終ジャッジ日時	2024-09-29 08:59:01
合計ジャッジ時間	15,285 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	3 ms 5,248 KB
testcase_02	AC	4 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	3 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	559 ms 14,848 KB
testcase_12	AC	543 ms 15,000 KB
testcase_13	AC	378 ms 14,720 KB
testcase_14	AC	530 ms 15,360 KB
testcase_15	AC	558 ms 15,412 KB
testcase_16	AC	595 ms 15,488 KB
testcase_17	AC	618 ms 15,616 KB
testcase_18	AC	613 ms 15,572 KB
testcase_19	AC	271 ms 15,368 KB
testcase_20	AC	276 ms 15,488 KB
testcase_21	AC	279 ms 15,332 KB
testcase_22	AC	285 ms 15,488 KB
testcase_23	AC	280 ms 15,360 KB
testcase_24	AC	248 ms 15,360 KB
testcase_25	AC	262 ms 15,548 KB
testcase_26	AC	268 ms 15,212 KB
testcase_27	AC	251 ms 15,556 KB
testcase_28	AC	261 ms 15,360 KB
testcase_29	AC	509 ms 15,376 KB
testcase_30	AC	544 ms 15,456 KB
testcase_31	AC	585 ms 15,288 KB
testcase_32	AC	98 ms 15,560 KB
testcase_33	AC	227 ms 15,360 KB
testcase_34	AC	243 ms 15,416 KB
testcase_35	AC	236 ms 15,488 KB
testcase_36	AC	231 ms 15,488 KB
testcase_37	AC	236 ms 15,488 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:291:41: warning: narrowing conversion of 'x' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  291 |     if(type == 1) { seg.apply(l, r, {0, x}); }
      |                                         ^
main.cpp:292:38: warning: narrowing conversion of 'x' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  292 |     if(type == 2) { seg.apply(l, r, {x, 0}); }
      |                                      ^

ソースコード

raw source code

#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 = 1LL << 30;
// 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) { return S(f.upd, x.sz); }
//   if(f.g) {
//     if(x.sz == 1) { return S(gcd(x.max, f.g)); }
//     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(); }

ll INF = 2e9;

struct S {
  int max_val;
  int lcm;
  int len;
  ll sum;
  bool fail;
};

S e() {
  return {0, 1, 0, 0, false};
}

S apply_reset(S original, int x) {
  return {x, x, original.len, (ll)original.len * x, false};
}

S op(S l, S r) {
  if(r.len == 0) return l;
  if(l.len == 0) return r;
  S ret = e();
  ret.max_val = max(l.max_val, r.max_val);
  ret.lcm = min(INF, (ll)l.lcm * r.lcm / __gcd(l.lcm, r.lcm));
  ret.len = l.len + r.len;
  ret.sum = l.sum + r.sum;
  return ret;
}

struct F {
  int dogcd;
  int reset;
};

F id() {
  return {0, 0};
}

S fx(F f, S x) {
  if(x.fail) return x;
  assert(!((f.reset > 0) && (f.dogcd > 0)));
  if(f.reset > 0) {
    return apply_reset(x, f.reset);
  }
  if(f.dogcd > 0) {
    if((ll)x.len * x.max_val == x.sum) {
      return apply_reset(x, __gcd(f.dogcd, x.max_val));
    }
    if(x.lcm == INF || f.dogcd % x.lcm > 0) {
      x.fail = 1;
      return x;
    }
  }
  return x;
}

F fg(F g, F f) {
  if(g.reset) {
    return {0, g.reset};
  }
  if(f.reset) {
    return {0, __gcd(g.dogcd, f.reset)};
  }
  return {__gcd(g.dogcd, f.dogcd), 0};
}

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] = apply_reset({0, 1, 1, 0}, 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, {0, x}); }
    if(type == 2) { seg.apply(l, r, {x, 0}); }
    if(type == 3) { cout << seg.prod(l, r).max_val << "\n"; }
    if(type == 4) { cout << seg.prod(l, r).sum << "\n"; }
  }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード