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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: gojoxd
• 提出日時: 2026-04-18 19:37:19
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 90 ms / 2,000 ms
• コード長: 3,855 bytes
• コンパイル時間: 1,212 ms
• コンパイル使用メモリ: 179,212 KB
• 実行使用メモリ: 12,928 KB
• 最終ジャッジ日時: 2026-04-18 19:37:28
• 合計ジャッジ時間: 7,347 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

struct Node {
    ll sum;
    ll max_val;
    ll min_val;
    ll lazy; // -1 indicates no pending range assignment
};

const int MAXN = 100005;
Node tree[4 * MAXN];
ll A[MAXN];

// Combine two child nodes to update the parent
void push_up(int node) {
    tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
    tree[node].max_val = max(tree[node * 2].max_val, tree[node * 2 + 1].max_val);
    tree[node].min_val = min(tree[node * 2].min_val, tree[node * 2 + 1].min_val);
}

// Apply a uniform assignment to a node
void apply_lazy(int node, int start, int end, ll val) {
    tree[node].sum = val * (end - start + 1);
    tree[node].max_val = val;
    tree[node].min_val = val;
    tree[node].lazy = val;
}

// Push pending assignments down to children
void push_down(int node, int start, int end) {
    if (tree[node].lazy != -1) {
        int mid = (start + end) / 2;
        apply_lazy(node * 2, start, mid, tree[node].lazy);
        apply_lazy(node * 2 + 1, mid + 1, end, tree[node].lazy);
        tree[node].lazy = -1; // clear the lazy tag
    }
}

// Build the initial segment tree
void build(int node, int start, int end) {
    tree[node].lazy = -1;
    if (start == end) {
        tree[node].sum = A[start];
        tree[node].max_val = A[start];
        tree[node].min_val = A[start];
        return;
    }
    int mid = (start + end) / 2;
    build(node * 2, start, mid);
    build(node * 2 + 1, mid + 1, end);
    push_up(node);
}

// Query 1: Range Assignment
void update_assign(int node, int start, int end, int l, int r, ll val) {
    if (r < start || end < l) return;
    if (l <= start && end <= r) {
        apply_lazy(node, start, end, val);
        return;
    }
    push_down(node, start, end);
    int mid = (start + end) / 2;
    update_assign(node * 2, start, mid, l, r, val);
    update_assign(node * 2 + 1, mid + 1, end, l, r, val);
    push_up(node);
}

// Query 2: Range isqrt
void update_sqrt(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return;
    
    // Optimization: if the segment only contains 0s and 1s, isqrt does nothing!
    if (tree[node].max_val <= 1) return;
    
    // If the segment is completely covered AND it's completely uniform
    if (l <= start && end <= r && tree[node].min_val == tree[node].max_val) {
        ll root = floor(sqrt(tree[node].max_val));
        apply_lazy(node, start, end, root);
        return;
    }
    
    // Otherwise, push down lazy assignments and recurse
    push_down(node, start, end);
    int mid = (start + end) / 2;
    update_sqrt(node * 2, start, mid, l, r);
    update_sqrt(node * 2 + 1, mid + 1, end, l, r);
    push_up(node);
}

// Query 0: Range Sum
ll query_sum(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node].sum;
    
    push_down(node, start, end);
    int mid = (start + end) / 2;
    return query_sum(node * 2, start, mid, l, r) + query_sum(node * 2 + 1, mid + 1, end, l, r);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, q;
    if (!(cin >> n >> q)) return 0;
    
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    
    if (n > 0) build(1, 0, n - 1);
    
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        r--; // Problem uses 0-indexed half-open intervals [l, r)
             // We convert to inclusive [l, r-1]
        
        if (type == 0) {
            cout << query_sum(1, 0, n - 1, l, r) << "\n";
        } else if (type == 1) {
            ll x;
            cin >> x;
            update_assign(1, 0, n - 1, l, r, x);
        } else if (type == 2) {
            update_sqrt(1, 0, n - 1, l, r);
        }
    }
    
    return 0;
}