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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: Naru820
• 提出日時: 2026-03-29 19:03:54
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 138 ms / 2,000 ms
• コード長: 3,451 bytes
• コンパイル時間: 3,934 ms
• コンパイル使用メモリ: 340,552 KB
• 実行使用メモリ: 8,960 KB
• 最終ジャッジ日時: 2026-04-17 19:52:35
• 合計ジャッジ時間: 13,167 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

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

using ll = long long;

struct SegTree {
    int n;
    vector<ll> sum;
    vector<int> mn, mx;
    vector<int> lazy; // -1 means no lazy assignment

    SegTree(const vector<int>& a) {
        n = 1;
        while (n < (int)a.size()) n <<= 1;
        sum.assign(2 * n, 0);
        mn.assign(2 * n, 0);
        mx.assign(2 * n, 0);
        lazy.assign(2 * n, -1);

        for (int i = 0; i < (int)a.size(); i++) {
            sum[n + i] = a[i];
            mn[n + i] = mx[n + i] = a[i];
        }
        for (int i = n - 1; i >= 1; i--) pull(i);
    }

    static int isqrt_int(int x) {
        int y = (int)floor(sqrt((long double)x));
        while ((ll)(y + 1) * (y + 1) <= x) y++;
        while ((ll)y * y > x) y--;
        return y;
    }

    void apply_assign(int k, int l, int r, int x) {
        sum[k] = 1LL * (r - l) * x;
        mn[k] = mx[k] = x;
        lazy[k] = x;
    }

    void push(int k, int l, int r) {
        if (lazy[k] == -1 || r - l == 1) return;
        int mid = (l + r) >> 1;
        apply_assign(k << 1, l, mid, lazy[k]);
        apply_assign(k << 1 | 1, mid, r, lazy[k]);
        lazy[k] = -1;
    }

    void pull(int k) {
        sum[k] = sum[k << 1] + sum[k << 1 | 1];
        mn[k] = min(mn[k << 1], mn[k << 1 | 1]);
        mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
    }

    void range_assign(int a, int b, int x) { range_assign(a, b, x, 1, 0, n); }
    void range_assign(int a, int b, int x, int k, int l, int r) {
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            apply_assign(k, l, r, x);
            return;
        }
        push(k, l, r);
        int mid = (l + r) >> 1;
        range_assign(a, b, x, k << 1, l, mid);
        range_assign(a, b, x, k << 1 | 1, mid, r);
        pull(k);
    }

    void range_sqrt(int a, int b) { range_sqrt(a, b, 1, 0, n); }
    void range_sqrt(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l || mx[k] <= 1) return;

        if (a <= l && r <= b && mn[k] == mx[k]) {
            int y = isqrt_int(mx[k]);
            apply_assign(k, l, r, y);
            return;
        }

        if (r - l == 1) {
            int y = isqrt_int(mx[k]);
            apply_assign(k, l, r, y);
            return;
        }

        push(k, l, r);
        int mid = (l + r) >> 1;
        range_sqrt(a, b, k << 1, l, mid);
        range_sqrt(a, b, k << 1 | 1, mid, r);
        pull(k);
    }

    ll range_sum(int a, int b) { return range_sum(a, b, 1, 0, n); }
    ll range_sum(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return sum[k];
        push(k, l, r);
        int mid = (l + r) >> 1;
        return range_sum(a, b, k << 1, l, mid)
             + range_sum(a, b, k << 1 | 1, mid, r);
    }
};

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

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    SegTree seg(A);

    while (Q--) {
        int t;
        cin >> t;
        if (t == 0) {
            int l, r;
            cin >> l >> r;
            cout << seg.range_sum(l, r) << '\n';
        } else if (t == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            seg.range_assign(l, r, x);
        } else {
            int l, r;
            cin >> l >> r;
            seg.range_sqrt(l, r);
        }
    }

    return 0;
}