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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: テナガザル
• 提出日時: 2026-04-18 01:42:22
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 299 ms / 2,000 ms
• コード長: 3,359 bytes
• コンパイル時間: 2,132 ms
• コンパイル使用メモリ: 189,004 KB
• 実行使用メモリ: 9,984 KB
• 最終ジャッジ日時: 2026-04-18 01:42:31
• 合計ジャッジ時間: 9,277 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

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

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

long long isqrt(long long x)
{
  long long res = sqrt(x);
  while ((res + 1) * (res + 1) <= x) ++res;
  while (res * res > x) --res;
  return res;
}

// https://nyaannyaan.github.io/library/segment-tree/segment-tree-beats-abstract.hpp
template <typename Node>
struct Beats {
  int n, log;
  vector<Node> v;

  template <typename T>
  Beats(vector<T>& vc) {
    n = 1, log = 0;
    while (n < (int)vc.size()) n <<= 1, log++;
    v.resize(2 * n);
    for (int i = 0; i < (int)vc.size(); ++i) v[i + n] = Node(vc[i]);
    for (int i = n - 1; i; --i) _update(i);
  }

  template <typename T>
  void apply(int l, int r, T x) {
    if (l == r) return;
    l += n, r += n;
    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) _apply(l++, x);
        if (r & 1) _apply(--r, x);
        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 <typename F>
  void query(int l, int r, const F& f) {
    if (l == r) return;
    l += n, r += n;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) _push(l >> i);
      if (((r >> i) << i) != r) _push((r - 1) >> i);
    }
    while (l < r) {
      if (l & 1) f(v[l++]);
      if (r & 1) f(v[--r]);
      l >>= 1;
      r >>= 1;
    }
  }

 private:
  void _push(int i) { v[i].push(v[2 * i + 0], v[2 * i + 1]); }
  void _update(int i) { v[i].update(v[2 * i + 0], v[2 * i + 1]); }
  template <typename T>
  void _apply(int i, T x) {
    bool res = v[i].apply(x);
    if (i < n && res == false) {
      _push(i);
      _apply(i * 2 + 0, x);
      _apply(i * 2 + 1, x);
      _update(i);
    }
  }
};

struct Node
{
  long long sum;
  int val;
  int siz;
  bool same;
  Node(int v = 0) : sum(v), val(v), siz(1), same(true) {}

  void query2(int x)
  {
    sum = x * (long long)siz;
    val = x;
    same = true;
  }
  void push(Node& l, Node& r)
  {
    if (same) l.query2(val), r.query2(val);
  }
  void update(Node& l, Node& r)
  {
    sum = l.sum + r.sum;
    val = l.val;
    siz = l.siz + r.siz;
    same = (l.same && r.same && l.val == r.val);
  }
  bool apply(pair<int, int> p)
  {
    if (p.first == 1)
    {
      if (same)
      {
        val = isqrt(val);
        sum = val * (long long)siz;
        return true;
      }
      else return false;
    }
    else
    {
      val = p.second;
      sum = val * (long long)siz;
      same = true;
      return true;
    }
  }
};

int main()
{
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  Beats<Node> sg(a);
  for (int i = 0; i < q; i++)
  {
    int t;
    cin >> t;
    if (t == 0)
    {
      int l, r;
      cin >> l >> r;
      long long ans = 0;
      sg.query(l, r, [&](Node& nd) {ans += nd.sum;});
      cout << ans << '\n';
    }
    else if (t == 1)
    {
      int l, r, x;
      cin >> l >> r >> x;
      sg.apply(l, r, make_pair(0, x));
    }
    else if (t == 2)
    {
      int l, r;
      cin >> l >> r;
      sg.apply(l, r, make_pair(1, 0));
    }
  }
}