結果

問題 No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー ,
提出日時 2026-04-19 12:24:25
言語 C++17(clang)
(clang++ 22.1.2 + boost 1.89.0)
コンパイル:
clang++ -O2 -lm -std=c++1z -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 3,365 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,865 ms
コンパイル使用メモリ 175,688 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2026-04-19 12:24:51
合計ジャッジ時間 6,550 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const ll NO_LAZY = -1;

struct Node { ll sum, mn, mx, lazy; };

int n, q;
Node tree[4 * MAXN];

void build(int node, int l, int r, vector<ll>& A) {
    tree[node].lazy = NO_LAZY;
    if (l + 1 == r) {
        tree[node].sum = tree[node].mn = tree[node].mx = A[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2*node, l, mid, A);
    build(2*node+1, mid, r, A);
    tree[node].sum = tree[2*node].sum + tree[2*node+1].sum;
    tree[node].mn = min(tree[2*node].mn, tree[2*node+1].mn);
    tree[node].mx = max(tree[2*node].mx, tree[2*node+1].mx);
}

void apply_assign(int node, int l, int r, ll val) {
    tree[node].sum = val * (ll)(r - l);
    tree[node].mn = tree[node].mx = val;
    tree[node].lazy = val;
}

void pushdown(int node, int l, int r) {
    if (tree[node].lazy != NO_LAZY) {
        int mid = (l + r) / 2;
        apply_assign(2*node,   l,   mid, tree[node].lazy);
        apply_assign(2*node+1, mid, r,   tree[node].lazy);
        tree[node].lazy = NO_LAZY;
    }
}

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

ll isqrt_safe(ll v) {
    if (v <= 0) return 0;
    ll s = (ll)sqrtl((long double)v);
    while (s * s > v) s--;
    while ((s+1)*(s+1) <= v) s++;
    return s;
}

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

void update_assign(int node, int l, int r, int ql, int qr, ll val) {
    if (ql <= l && r <= qr) { apply_assign(node, l, r, val); return; }
    pushdown(node, l, r);
    int mid = (l + r) / 2;
    if (ql < mid) update_assign(2*node,   l,   mid, ql, qr, val);
    if (qr > mid) update_assign(2*node+1, mid, r,   ql, qr, val);
    pull(node);
}

void update_isqrt(int node, int l, int r, int ql, int qr) {
    if (ql >= r || l >= qr) return;
    ll sq_mn = isqrt_safe(tree[node].mn);
    ll sq_mx = isqrt_safe(tree[node].mx);
    if (ql <= l && r <= qr && sq_mn == sq_mx) {
        apply_assign(node, l, r, sq_mn);
        return;
    }
    if (l + 1 == r) {
        tree[node].sum = tree[node].mn = tree[node].mx = sq_mn;
        tree[node].lazy = NO_LAZY;
        return;
    }
    pushdown(node, l, r);
    int mid = (l + r) / 2;
    update_isqrt(2*node,   l,   mid, ql, qr);
    update_isqrt(2*node+1, mid, r,   ql, qr);
    pull(node);
}

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

    cin >> n >> q;
    vector<ll> A(n);
    for (int i = 0; i < n; i++) cin >> A[i];

    build(1, 0, n, A);

    while (q--) {
        int type;
        cin >> type;
        if (type == 0) {
            int l, r;
            cin >> l >> r;
            cout << query_sum(1, 0, n, l, r) << '\n';
        } else if (type == 1) {
            int l, r; ll x;
            cin >> l >> r >> x;
            update_assign(1, 0, n, l, r, x);
        } else {
            int l, r;
            cin >> l >> r;
            update_isqrt(1, 0, n, l, r);
        }
    }
    return 0;
}
0