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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: よいちなすの
• 提出日時: 2026-04-18 04:38:50
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 108 ms / 2,000 ms
• コード長: 4,218 bytes
• コンパイル時間: 2,968 ms
• コンパイル使用メモリ: 341,824 KB
• 実行使用メモリ: 16,504 KB
• 最終ジャッジ日時: 2026-04-18 04:39:08
• 合計ジャッジ時間: 8,892 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

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

ソースコード

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


long long isqrt(long long x) {
    if (x <= 0) return 0;
    long long r = (long long)sqrt((double)x);
    while ((r + 1) * (r + 1) <= x) r++;
    while (r * r > x) r--;
    return r;
}

struct Node {
    long long sum;
    long long mx;
    long long mn;
    long long lz_set; 
    long long lz_add;
    int size;

    Node() : sum(0), mx(0), mn(2e18), lz_set(-1), lz_add(0), size(0) {}
};

class LzSeg {
    int n;
    vector<Node> tree;

    void push_up(int node) {
        tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;
        tree[node].mx = max(tree[2 * node].mx, tree[2 * node + 1].mx);
        tree[node].mn = min(tree[2 * node].mn, tree[2 * node + 1].mn);
    }

    void X(int node, long long val) {
        tree[node].sum = val * tree[node].size;
        tree[node].mx = val;
        tree[node].mn = val;
        tree[node].lz_set = val;
        tree[node].lz_add = 0;
    }

    void apply_add(int node, long long val) {
        tree[node].sum += val * tree[node].size;
        tree[node].mx += val;
        tree[node].mn += val;
        tree[node].lz_add += val;
    }

    void push_down(int node) {
        if (tree[node].lz_set != -1) {
            X(2 * node, tree[node].lz_set);
            X(2 * node + 1, tree[node].lz_set);
            tree[node].lz_set = -1;
        }
        if (tree[node].lz_add != 0) {
            apply_add(2 * node, tree[node].lz_add);
            apply_add(2 * node + 1, tree[node].lz_add);
            tree[node].lz_add = 0;
        }
    }

public:
    LzSeg(const vector<long long>& a) {
        int sz = a.size();
        n = 1;
        while (n < sz) n *= 2;
        tree.resize(2 * n);
        for (int i = 0; i < sz; i++) {
            tree[n + i].sum = tree[n + i].mx = tree[n + i].mn = a[i];
            tree[n + i].size = 1;
        }
        for (int i = n - 1; i >= 1; i--) {
            tree[i].size = tree[2 * i].size + tree[2 * i + 1].size;
            push_up(i);
        }
    }

    void range_set(int node, int l, int r, int ql, int qr, long long x) {
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) {
            X(node, x);
            return;
        }
        push_down(node);
        int mid = (l + r) / 2;
        range_set(2 * node, l, mid, ql, qr, x);
        range_set(2 * node + 1, mid, r, ql, qr, x);
        push_up(node);
    }

    void range_sqrt(int node, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql || tree[node].mx <= 1 && tree[node].mx == tree[node].mn) return;
        if (ql <= l && r <= qr) {
            if (tree[node].mx == tree[node].mn) {
                X(node, isqrt(tree[node].mx));
                return;
            }
            if (tree[node].mx == tree[node].mn + 1) {
                long long s1 = isqrt(tree[node].mx);
                long long s2 = isqrt(tree[node].mn);
                if (s1 == s2 + 1) {
                    apply_add(node, s1 - tree[node].mx);
                    return;
                }
            }
        }
        push_down(node);
        int mid = (l + r) / 2;
        range_sqrt(2 * node, l, mid, ql, qr);
        range_sqrt(2 * node + 1, mid, r, ql, qr);
        push_up(node);
    }

    long long query_sum(int node, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) return 0;
        if (ql <= l && r <= qr) return tree[node].sum;
        push_down(node);
        int mid = (l + r) / 2;
        return query_sum(2 * node, l, mid, ql, qr) + query_sum(2 * node + 1, mid, r, ql, qr);
    }

    int get_leaf_count() { return n; }
};

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

    int N, Q;
    cin >> N >> Q;

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

    LzSeg st(A);
    int Y = st.get_leaf_count();

    for (int i = 0; i < Q; i++) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 0) {
            cout << st.query_sum(1, 0, Y, l, r) << "\n";
        } else if (type == 1) {
            long long x;
            cin >> x;
            st.range_set(1, 0, Y, l, r, x);
        } else if (type == 2) {
            st.range_sqrt(1, 0, Y, l, r);
        }
    }

    return 0;
}