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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: e032_Ashmit_Rana
• 提出日時: 2026-04-18 01:32:04
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 152 ms / 2,000 ms
• コード長: 5,273 bytes
• コンパイル時間: 2,376 ms
• コンパイル使用メモリ: 341,540 KB
• 実行使用メモリ: 19,840 KB
• 最終ジャッジ日時: 2026-04-18 01:32:14
• 合計ジャッジ時間: 9,524 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

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

ソースコード

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

using int64 = long long;

struct SegmentTree {
    static constexpr int64 NO_SET = -1;

    int n;
    vector<int64> total;
    vector<int64> mn;
    vector<int64> mx;
    vector<int64> lazy_set;
    vector<int64> lazy_add;

    explicit SegmentTree(const vector<int64>& a) : n((int)a.size()) {
        int size = 4 * max(1, n) + 5;
        total.assign(size, 0);
        mn.assign(size, 0);
        mx.assign(size, 0);
        lazy_set.assign(size, NO_SET);
        lazy_add.assign(size, 0);
        build(1, 0, n, a);
    }

    static int64 isqrt_int(int64 x) {
        int64 r = (int64)sqrt((long double)x);
        while ((r + 1) * (r + 1) <= x) ++r;
        while (r * r > x) --r;
        return r;
    }

    void pull(int v) {
        int left_child = v << 1;
        int right_child = left_child | 1;
        total[v] = total[left_child] + total[right_child];
        mn[v] = min(mn[left_child], mn[right_child]);
        mx[v] = max(mx[left_child], mx[right_child]);
    }

    void apply_set(int v, int left, int right, int64 value) {
        total[v] = value * (right - left);
        mn[v] = value;
        mx[v] = value;
        lazy_set[v] = value;
        lazy_add[v] = 0;
    }

    void apply_add(int v, int left, int right, int64 delta) {
        total[v] += delta * (right - left);
        mn[v] += delta;
        mx[v] += delta;
        if (lazy_set[v] != NO_SET) {
            lazy_set[v] += delta;
        } else {
            lazy_add[v] += delta;
        }
    }

    void push(int v, int left, int right) {
        if (right - left == 1) {
            lazy_set[v] = NO_SET;
            lazy_add[v] = 0;
            return;
        }

        int mid = (left + right) >> 1;
        int left_child = v << 1;
        int right_child = left_child | 1;

        if (lazy_set[v] != NO_SET) {
            apply_set(left_child, left, mid, lazy_set[v]);
            apply_set(right_child, mid, right, lazy_set[v]);
            lazy_set[v] = NO_SET;
        }

        if (lazy_add[v] != 0) {
            apply_add(left_child, left, mid, lazy_add[v]);
            apply_add(right_child, mid, right, lazy_add[v]);
            lazy_add[v] = 0;
        }
    }

    void build(int v, int left, int right, const vector<int64>& a) {
        if (right - left == 1) {
            total[v] = mn[v] = mx[v] = a[left];
            return;
        }

        int mid = (left + right) >> 1;
        build(v << 1, left, mid, a);
        build(v << 1 | 1, mid, right, a);
        pull(v);
    }

    void range_set(int ql, int qr, int64 value) {
        if (ql < qr) range_set(1, 0, n, ql, qr, value);
    }

    void range_set(int v, int left, int right, int ql, int qr, int64 value) {
        if (qr <= left || right <= ql) return;
        if (ql <= left && right <= qr) {
            apply_set(v, left, right, value);
            return;
        }

        push(v, left, right);
        int mid = (left + right) >> 1;
        range_set(v << 1, left, mid, ql, qr, value);
        range_set(v << 1 | 1, mid, right, ql, qr, value);
        pull(v);
    }

    void range_sqrt(int ql, int qr) {
        if (ql < qr) range_sqrt(1, 0, n, ql, qr);
    }

    void range_sqrt(int v, int left, int right, int ql, int qr) {
        if (qr <= left || right <= ql || mx[v] <= 1) return;

        if (ql <= left && right <= qr) {
            int64 low = mn[v];
            int64 high = mx[v];
            int64 sqrt_low = isqrt_int(low);
            int64 sqrt_high = isqrt_int(high);

            if (sqrt_low == sqrt_high) {
                apply_set(v, left, right, sqrt_low);
                return;
            }

            int64 delta_low = sqrt_low - low;
            if (delta_low == sqrt_high - high) {
                apply_add(v, left, right, delta_low);
                return;
            }

            if (right - left == 1) {
                apply_set(v, left, right, sqrt_low);
                return;
            }
        }

        push(v, left, right);
        int mid = (left + right) >> 1;
        range_sqrt(v << 1, left, mid, ql, qr);
        range_sqrt(v << 1 | 1, mid, right, ql, qr);
        pull(v);
    }

    int64 range_sum(int ql, int qr) {
        return range_sum(1, 0, n, ql, qr);
    }

    int64 range_sum(int v, int left, int right, int ql, int qr) {
        if (qr <= left || right <= ql) return 0;
        if (ql <= left && right <= qr) return total[v];

        push(v, left, right);
        int mid = (left + right) >> 1;
        return range_sum(v << 1, left, mid, ql, qr) +
               range_sum(v << 1 | 1, mid, right, ql, qr);
    }
};

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

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<int64> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    SegmentTree seg(a);

    for (int i = 0; i < q; ++i) {
        int type;
        int left;
        int right;
        cin >> type >> left >> right;

        if (type == 0) {
            cout << seg.range_sum(left, right) << '\n';
        } else if (type == 1) {
            int64 value;
            cin >> value;
            seg.range_set(left, right, value);
        } else {
            seg.range_sqrt(left, right);
        }
    }

    return 0;
}