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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: rumblycascade7
• 提出日時: 2026-04-18 06:03:47
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 135 ms / 2,000 ms
• コード長: 4,816 bytes
• コンパイル時間: 2,609 ms
• コンパイル使用メモリ: 344,900 KB
• 実行使用メモリ: 10,880 KB
• 最終ジャッジ日時: 2026-04-18 06:03:54
• 合計ジャッジ時間: 6,879 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

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

using ll = long long;

struct SegTree {
    int sz;
    vector<ll> sm;
    vector<int> mn, mx;
    vector<int> setlz, addlz;
    vector<char> hasSet;

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

        sm.assign(sz << 1, 0);
        mn.assign(sz << 1, 0);
        mx.assign(sz << 1, 0);
        setlz.assign(sz << 1, 0);
        addlz.assign(sz << 1, 0);
        hasSet.assign(sz << 1, 0);

        for (int i = 0; i < sz; i++) {
            int v = (i < (int)a.size() ? a[i] : 0);
            sm[sz + i] = v;
            mn[sz + i] = v;
            mx[sz + i] = v;
        }

        for (int i = sz - 1; i >= 1; i--) pull(i);
    }

    inline void pull(int i) {
        int lc = i << 1;
        int rc = lc | 1;
        sm[i] = sm[lc] + sm[rc];
        mn[i] = min(mn[lc], mn[rc]);
        mx[i] = max(mx[lc], mx[rc]);
    }

    inline void apply_set(int i, int l, int r, int v) {
        sm[i] = 1LL * v * (r - l);
        mn[i] = v;
        mx[i] = v;
        hasSet[i] = 1;
        setlz[i] = v;
        addlz[i] = 0;
    }

    inline void apply_add(int i, int l, int r, int d) {
        if (d == 0) return;

        sm[i] += 1LL * d * (r - l);
        mn[i] += d;
        mx[i] += d;

        if (hasSet[i]) setlz[i] += d;
        else addlz[i] += d;
    }

    inline void push(int i, int l, int r) {
        if (r - l == 1) {
            hasSet[i] = 0;
            addlz[i] = 0;
            return;
        }

        int mid = (l + r) >> 1;
        int lc = i << 1;
        int rc = lc | 1;

        if (hasSet[i]) {
            int v = setlz[i];
            apply_set(lc, l, mid, v);
            apply_set(rc, mid, r, v);
            hasSet[i] = 0;
        }

        if (addlz[i] != 0) {
            int d = addlz[i];
            apply_add(lc, l, mid, d);
            apply_add(rc, mid, r, d);
            addlz[i] = 0;
        }
    }

    void upd_set(int ql, int qr, int v, int i, int l, int r) {
        if (qr <= l || r <= ql) return;

        if (ql <= l && r <= qr) {
            apply_set(i, l, r, v);
            return;
        }

        push(i, l, r);
        int mid = (l + r) >> 1;

        upd_set(ql, qr, v, i << 1, l, mid);
        upd_set(ql, qr, v, i << 1 | 1, mid, r);

        pull(i);
    }

    ll get_sum(int ql, int qr, int i, int l, int r) {
        if (qr <= l || r <= ql) return 0;

        if (ql <= l && r <= qr) return sm[i];

        push(i, l, r);
        int mid = (l + r) >> 1;

        return get_sum(ql, qr, i << 1, l, mid) + get_sum(ql, qr, i << 1 | 1, mid, r);
    }

    void upd_sqrt(int ql, int qr, int i, int l, int r) {
        if (qr <= l || r <= ql) return;
        if (mx[i] <= 1) return;

        if (ql <= l && r <= qr) {
            int d1 = (int)std::sqrt((double)mn[i]) - mn[i];
            while (1LL * (mn[i] + d1 + 1) * (mn[i] + d1 + 1) <= mn[i]) d1++;
            while (1LL * (mn[i] + d1) * (mn[i] + d1) > mn[i]) d1--;
            d1 = (int)std::sqrt((double)mn[i]) - mn[i];

            int d2 = (int)std::sqrt((double)mx[i]) - mx[i];
            while (1LL * (mx[i] + d2 + 1) * (mx[i] + d2 + 1) <= mx[i]) d2++;
            while (1LL * (mx[i] + d2) * (mx[i] + d2) > mx[i]) d2--;
            d2 = (int)std::sqrt((double)mx[i]) - mx[i];

            if (d1 == d2) {
                apply_add(i, l, r, d1);
                return;
            }
        }

        if (r - l == 1) {
            int nv = (int)std::sqrt((double)mx[i]);
            while (1LL * (nv + 1) * (nv + 1) <= mx[i]) nv++;
            while (1LL * nv * nv > mx[i]) nv--;
            apply_set(i, l, r, nv);
            return;
        }

        push(i, l, r);
        int mid = (l + r) >> 1;

        upd_sqrt(ql, qr, i << 1, l, mid);
        upd_sqrt(ql, qr, i << 1 | 1, mid, r);

        pull(i);
    }

    void upd_set(int l, int r, int v) {
        upd_set(l, r, v, 1, 0, sz);
    }

    ll get_sum(int l, int r) {
        return get_sum(l, r, 1, 0, sz);
    }

    void upd_sqrt(int l, int r) {
        upd_sqrt(l, r, 1, 0, sz);
    }
};

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);
    vector<ll> ans;
    ans.reserve(q);

    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;

        if (t == 0) {
            int l, r;
            cin >> l >> r;
            ans.push_back(seg.get_sum(l, r));
        }
        else if (t == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            seg.upd_set(l, r, x);
        }
        else {
            int l, r;
            cin >> l >> r;
            seg.upd_sqrt(l, r);
        }
    }

    for (auto x : ans) cout << x << '\n';

    return 0;
}