結果

問題 No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー ,
提出日時 2026-04-19 12:21:08
言語 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,631 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,988 ms
コンパイル使用メモリ 175,048 KB
実行使用メモリ 12,800 KB
最終ジャッジ日時 2026-04-19 12:21:34
合計ジャッジ時間 7,350 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28 RE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:110:10: warning: variable length arrays in C++ are a Clang extension [-Wvla-cxx-extension]
  110 |     ll A[n];
      |          ^
main.cpp:110:10: note: read of non-const variable 'n' is not allowed in a constant expression
main.cpp:14:5: note: declared here
   14 | int n, q;
      |     ^
1 warning generated.

ソースコード

diff #
raw source code 

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

typedef long long ll;

const int MAXN = 100005;
const ll INF = -1; // no lazy assign pending

struct Node {
    ll sum, mn, mx;
    ll lazy; // -1 = no pending assign
};

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

void build(int node, int l, int r, ll* A) {
    tree[node].lazy = INF;
    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 pushdown_assign(int node, int l, int r, ll val) {
    int len = r - l;
    tree[node].sum = val * len;
    tree[node].mn = tree[node].mx = val;
    tree[node].lazy = val;
}

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

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

// Query 0: range sum
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;
}

// Query 1: range assign
void update_assign(int node, int l, int r, int ql, int qr, ll val) {
    if (ql <= l && r <= qr) {
        pushdown_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);
}

// Query 2: range isqrt
void update_isqrt(int node, int l, int r, int ql, int qr) {
    if (ql >= r || l >= qr) return;
    // If min and max have same isqrt, treat as range assign
    ll sq_mn = (ll)sqrtl(tree[node].mn);
    while (sq_mn * sq_mn > tree[node].mn) sq_mn--;
    while ((sq_mn+1)*(sq_mn+1) <= tree[node].mn) sq_mn++;
    ll sq_mx = (ll)sqrtl(tree[node].mx);
    while (sq_mx * sq_mx > tree[node].mx) sq_mx--;
    while ((sq_mx+1)*(sq_mx+1) <= tree[node].mx) sq_mx++;
    
    if (ql <= l && r <= qr && sq_mn == sq_mx) {
        pushdown_assign(node, l, r, sq_mn);
        return;
    }
    if (l + 1 == r) {
        // leaf
        tree[node].sum = tree[node].mn = tree[node].mx = sq_mn;
        tree[node].lazy = INF;
        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;
    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