#1160522 (C++23) No.3507 RangeSum RangeUpdate RangeSqrt

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: KowerKoint2010
• 提出日時: 2026-04-19 15:53:24
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 669 ms / 2,000 ms
• コード長: 5,040 bytes
• コンパイル時間: 2,623 ms
• コンパイル使用メモリ: 344,936 KB
• 実行使用メモリ: 30,848 KB
• 最終ジャッジ日時: 2026-04-19 15:53:47
• 合計ジャッジ時間: 16,669 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

ファイルパターン	結果
sample	AC * 1
other	AC * 29

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i, n) for(ll i =0; i < ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B>
bool chmax(A& a, B b) { return a<b && (a=b, true); }
template <class A, class B>
bool chmin(A& a, B b) { return b<a && (a=b, true); }

constexpr ll L = 7;

ll isqrt(ll a) {
  ll r = sqrt(a);
  while(r*r > a) r--;
  while((r+1)*(r+1) <= a) r++;
  return r;
}

struct S {
  array<ll, L> v;
  ll num_nonzero;
  ll sz;
};
S construct_s(ll x, ll sz) {
  S res;
  res.num_nonzero = (x > 0 ? sz : 0LL);
  res.sz = sz;
  REP(i, L) {
    res.v[i] = x * sz;
    x = isqrt(x);
  }
  return res;
}
S op(S x, S y) {
  S ret;
  ret.sz = x.sz + y.sz;
  ret.num_nonzero = x.num_nonzero + y.num_nonzero;
  REP(i, L) ret.v[i] = x.v[i] + y.v[i];
  return ret;
}
using F = pair<int, ll>;
S mapping(F f, S x) {
  if(f.first == 0) return construct_s(f.second, x.sz);
  S res;
  res.num_nonzero = x.num_nonzero;
  res.sz = x.sz;
  REP(i, L) {
    if(i+f.second < L) res.v[i] = x.v[i+f.second];
    else res.v[i] = x.num_nonzero;
  }
  return res;
}
F composition(F f, F g) {
  if(f.first == 0) return f;
  if(g.first == 0) {
    REP(i, f.second) g.second = isqrt(g.second);
    return g;
  }
  g.second += f.second;
  return g;
}

template <class S, class F, S op(S, S),
          F composition(F, F), S mapping(F, S)>
struct LazySegtree {
  int n, s, log;
  S e;
  F id;
  V<S> d;
  V<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 < s) 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;
  }
  
  LazySegtree() = default;
  LazySegtree(unsigned n, S e, F id)
      : n(n), s(bit_ceil(n)), e(e), id(id) {
    log = countr_zero((unsigned)s);
    d.assign(2 * s, e), lz.assign(s, id);
  }
  LazySegtree(const vector<S>& v, S e, F id)
      : LazySegtree(v.size(), e, id) {
    ranges::copy(v, d.begin() + s);
    for (int i = s - 1; i >= 1; i--) update(i);
  }
  void set(int p, S x) {
    p += s;
    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) {
    p += s;
    for (int i = log; i >= 1; i--) push(p >> i);
    return d[p];
  }
  S prod(int l, int r) {
    if (l == r) return e;
    l += s, r += s;
    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);
  }
  void apply(int l, int r, F f) {
    if (l == r) return;
    l += s, r += s;
    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 <class G>
  int max_right(int l, G g) {
    if (l == n) return n;
    l += s;
    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 < s) {
          push(l);
          l = 2 * l;
          if (g(op(sm, d[l]))) {
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - s;
      }
      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) {
    if (r == 0) return 0;
    r += s;
    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 < s) {
          push(r);
          r = 2 * r + 1;
          if (g(op(d[r], sm))) {
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - s;
      }
      sm = op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }
};

void testcase() {
  int n, q; cin >> n >> q;
  V<S> iv(n);
  REP(i, n) {
    ll a; cin >> a;
    iv[i] = construct_s(a, 1);
  }
  LazySegtree<S, F, op, composition, mapping> seg(iv, construct_s(0, 0), F{1, 0});
  while(q--) {
    int op, l, r; cin >> op >> l >> r;
    if(op == 0) {
      cout << seg.prod(l, r).v[0] << '\n';
    } else if(op == 1) {
      ll x; cin >> x;
      seg.apply(l, r, F{0, x});
    } else {
      seg.apply(l, r, F{1, 1});
    }
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  testcase();
}