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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: 왕지후
• 提出日時: 2026-04-18 11:31:36
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 103 ms / 2,000 ms
• コード長: 4,104 bytes
• コンパイル時間: 2,042 ms
• コンパイル使用メモリ: 188,960 KB
• 実行使用メモリ: 18,244 KB
• 最終ジャッジ日時: 2026-04-18 11:31:51
• 合計ジャッジ時間: 8,342 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_1

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

ソースコード

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

using namespace std;

struct Node {
    long long sum;
    long long max_val;
    long long min_val;
    long long lazy_set;
};

int N, Q;
vector<Node> tree;
vector<int> len;

// セグメント木の初期化
void build(int node, int start, int end, const vector<long long>& A) {
    len[node] = end - start;
    tree[node].lazy_set = -1; // -1 は遅延評価なしを意味する
    if (start == end - 1) {
        tree[node].sum = A[start];
        tree[node].max_val = A[start];
        tree[node].min_val = A[start];
        return;
    }
    int mid = start + (end - start) / 2;
    build(2 * node, start, mid, A);
    build(2 * node + 1, mid, end, A);
    tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;
    tree[node].max_val = max(tree[2 * node].max_val, tree[2 * node + 1].max_val);
    tree[node].min_val = min(tree[2 * node].min_val, tree[2 * node + 1].min_val);
}

// ノードに代入操作を適用する
void apply_set(int node, long long val) {
    tree[node].sum = val * len[node];
    tree[node].max_val = val;
    tree[node].min_val = val;
    tree[node].lazy_set = val;
}

// 遅延タグを下の子に伝播させる
void push_down(int node) {
    if (tree[node].lazy_set != -1) {
        apply_set(2 * node, tree[node].lazy_set);
        apply_set(2 * node + 1, tree[node].lazy_set);
        tree[node].lazy_set = -1;
    }
}

// クエリ1：区間代入 [l, r) を x にする
void update_set(int node, int start, int end, int l, int r, long long val) {
    if (l >= end || r <= start) return;
    if (l <= start && end <= r) {
        apply_set(node, val);
        return;
    }
    push_down(node);
    int mid = start + (end - start) / 2;
    update_set(2 * node, start, mid, l, r, val);
    update_set(2 * node + 1, mid, end, l, r, val);
    tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;
    tree[node].max_val = max(tree[2 * node].max_val, tree[2 * node + 1].max_val);
    tree[node].min_val = min(tree[2 * node].min_val, tree[2 * node + 1].min_val);
}

// クエリ2：区間の平方根 [l, r)
void update_sqrt(int node, int start, int end, int l, int r) {
    if (l >= end || r <= start) return;
    
    // 区間が完全に含まれている場合
    if (l <= start && end <= r) {
        if (tree[node].max_val <= 1) return; // 1以下なら何もしない
        if (tree[node].max_val == tree[node].min_val) { // 全て同じ値なら区間代入として扱う
            long long s = sqrt(tree[node].max_val);
            apply_set(node, s);
            return;
        }
    }
    
    push_down(node);
    int mid = start + (end - start) / 2;
    update_sqrt(2 * node, start, mid, l, r);
    update_sqrt(2 * node + 1, mid, end, l, r);
    tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;
    tree[node].max_val = max(tree[2 * node].max_val, tree[2 * node + 1].max_val);
    tree[node].min_val = min(tree[2 * node].min_val, tree[2 * node + 1].min_val);
}

// クエリ0：区間和 [l, r) の取得
long long query_sum(int node, int start, int end, int l, int r) {
    if (l >= end || r <= start) return 0;
    if (l <= start && end <= r) return tree[node].sum;
    push_down(node);
    int mid = start + (end - start) / 2;
    return query_sum(2 * node, start, mid, l, r) + query_sum(2 * node + 1, mid, end, l, r);
}

int main() {
    // 高速な入出力のためのおまじない
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> Q)) return 0;

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

    tree.resize(4 * N);
    len.resize(4 * N);
    build(1, 0, N, A);

    for (int i = 0; i < Q; i++) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 0) {
            cout << query_sum(1, 0, N, l, r) << "\n";
        } else if (type == 1) {
            long long x;
            cin >> x;
            update_set(1, 0, N, l, r, x);
        } else if (type == 2) {
            update_sqrt(1, 0, N, l, r);
        }
    }

    return 0;
}