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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: sient
• 提出日時: 2026-04-19 01:00:53
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 255 ms / 2,000 ms
• コード長: 3,813 bytes
• コンパイル時間: 3,004 ms
• コンパイル使用メモリ: 339,608 KB
• 実行使用メモリ: 12,032 KB
• 最終ジャッジ日時: 2026-04-19 01:01:04
• 合計ジャッジ時間: 9,693 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_1

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

ソースコード

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

struct SegTree {
    struct Node {
        long long sum = 0;
        int mn = 0, mx = 0;
        int add = 0;
        int setv = 0;
        bool has_set = false;
    };

    int n, size;
    vector<Node> st;

    SegTree(const vector<int>& a) {
        n = (int)a.size();
        size = 1;
        while (size < n) size <<= 1;
        st.resize(size << 1);

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

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

    void apply_set(int p, int l, int r, int v) {
        st[p].sum = 1LL * (r - l) * v;
        st[p].mn = st[p].mx = v;
        st[p].has_set = true;
        st[p].setv = v;
        st[p].add = 0;
    }

    void apply_add(int p, int l, int r, int d) {
        st[p].sum += 1LL * (r - l) * d;
        st[p].mn += d;
        st[p].mx += d;
        if (st[p].has_set) st[p].setv += d;
        else st[p].add += d;
    }

    void push(int p, int l, int r) {
        if (r - l == 1) return;
        int m = (l + r) >> 1;

        if (st[p].has_set) {
            apply_set(p << 1, l, m, st[p].setv);
            apply_set(p << 1 | 1, m, r, st[p].setv);
            st[p].has_set = false;
        }
        if (st[p].add != 0) {
            apply_add(p << 1, l, m, st[p].add);
            apply_add(p << 1 | 1, m, r, st[p].add);
            st[p].add = 0;
        }
    }

    void range_set(int ql, int qr, int v, int p, int l, int r) {
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) {
            apply_set(p, l, r, v);
            return;
        }
        push(p, l, r);
        int m = (l + r) >> 1;
        range_set(ql, qr, v, p << 1, l, m);
        range_set(ql, qr, v, p << 1 | 1, m, r);
        pull(p);
    }

    void range_sqrt(int ql, int qr, int p, int l, int r) {
        if (qr <= l || r <= ql || st[p].mx <= 1) return;

        if (ql <= l && r <= qr) {
            if (st[p].mn == st[p].mx) {
                apply_set(p, l, r, (int)floor(sqrt((long double)st[p].mx)));
                return;
            }
            int d1 = (int)floor(sqrt((long double)st[p].mn)) - st[p].mn;
            int d2 = (int)floor(sqrt((long double)st[p].mx)) - st[p].mx;
            if (d1 == d2) {
                apply_add(p, l, r, d1);
                return;
            }
        }

        push(p, l, r);
        int m = (l + r) >> 1;
        range_sqrt(ql, qr, p << 1, l, m);
        range_sqrt(ql, qr, p << 1 | 1, m, r);
        pull(p);
    }

    long long range_sum(int ql, int qr, int p, int l, int r) {
        if (qr <= l || r <= ql) return 0;
        if (ql <= l && r <= qr) return st[p].sum;
        push(p, l, r);
        int m = (l + r) >> 1;
        return range_sum(ql, qr, p << 1, l, m) + range_sum(ql, qr, p << 1 | 1, m, r);
    }

    void range_set(int l, int r, int v) { range_set(l, r, v, 1, 0, size); }
    void range_sqrt(int l, int r) { range_sqrt(l, r, 1, 0, size); }
    long long range_sum(int l, int r) { return range_sum(l, r, 1, 0, size); }
};

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, l, r;
        cin >> t >> l >> r;
        if (t == 0) {
            cout << seg.range_sum(l, r) << '\n';
        } else if (t == 1) {
            int x;
            cin >> x;
            seg.range_set(l, r, x);
        } else {
            seg.range_sqrt(l, r);
        }
    }

    return 0;
}