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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: Naru820
• 提出日時: 2026-03-29 18:24:53
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,184 bytes
• コンパイル時間: 1,749 ms
• コンパイル使用メモリ: 181,924 KB
• 実行使用メモリ: 12,672 KB
• 最終ジャッジ日時: 2026-04-17 19:51:59
• 合計ジャッジ時間: 9,886 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 22 WA * 7

ソースコード

//gemini 3.1 pro test
#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; // 区間代入用の遅延タグ (-1は遅延なし)
};

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

// 整数平方根
inline long long isqrt(long long x) {
    return (long long)sqrt(x);
}

// 子ノードの情報を親ノードにマージ
void push_up(int node) {
    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_assign(int node, int l, int r, long long val) {
    tree[node].sum = (long long)(r - l + 1) * val;
    tree[node].max_val = val;
    tree[node].min_val = val;
    tree[node].lazy = val;
}

// 遅延タグを子ノードに伝搬する関数
void push_down(int node, int l, int r) {
    if (tree[node].lazy != -1) {
        int mid = l + (r - l) / 2;
        apply_assign(2 * node, l, mid, tree[node].lazy);
        apply_assign(2 * node + 1, mid + 1, r, tree[node].lazy);
        tree[node].lazy = -1;
    }
}

// セグメント木の初期構築
void build(int node, int l, int r) {
    tree[node].lazy = -1;
    if (l == r) {
        tree[node].sum = A[l];
        tree[node].max_val = A[l];
        tree[node].min_val = A[l];
        return;
    }
    int mid = l + (r - l) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    push_up(node);
}

// クエリ1：区間代入
void update_assign(int node, int l, int r, int ql, int qr, long long val) {
    if (ql <= l && r <= qr) {
        apply_assign(node, l, r, val);
        return;
    }
    push_down(node, l, r);
    int mid = l + (r - l) / 2;
    if (ql <= mid) update_assign(2 * node, l, mid, ql, qr, val);
    if (qr > mid) update_assign(2 * node + 1, mid + 1, r, ql, qr, val);
    push_up(node);
}

// クエリ2：区間平方根
void update_isqrt(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        // 枝刈り1: 全て1以下なら値は変わらない
        if (tree[node].max_val <= 1) return;
        
        // 枝刈り2: 区間内の値がすべて同じなら、区間代入で一括処理
        if (tree[node].max_val == tree[node].min_val) {
            apply_assign(node, l, r, isqrt(tree[node].max_val));
            return;
        }
    }
    push_down(node, l, r);
    int mid = l + (r - l) / 2;
    if (ql <= mid) update_isqrt(2 * node, l, mid, ql, qr);
    if (qr > mid) update_isqrt(2 * node + 1, mid + 1, r, ql, qr);
    push_up(node);
}

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

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];
    }

    build(1, 0, N - 1);

    for (int i = 0; i < Q; ++i) {
        int type, l, r;
        cin >> type >> l >> r;
        
        // l == r の場合は空区間なので何も行わない、和は0
        if (l == r) {
            if (type == 0) cout << 0 << "\n";
            continue;
        }
        
        // 問題の l <= i < r は、閉区間で [l, r-1] となる
        int ql = l;
        int qr = r - 1;

        if (type == 0) {
            cout << query_sum(1, 0, N - 1, ql, qr) << "\n";
        } else if (type == 1) {
            long long x;
            cin >> x;
            update_assign(1, 0, N - 1, ql, qr, x);
        } else if (type == 2) {
            update_isqrt(1, 0, N - 1, ql, qr);
        }
    }

    return 0;
}