結果

問題 No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー Shiny
提出日時 2026-04-18 01:26:48
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 3,094 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 419 ms
コンパイル使用メモリ 20,696 KB
実行使用メモリ 35,992 KB
最終ジャッジ日時 2026-04-18 01:27:32
合計ジャッジ時間 9,952 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 2 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from math import isqrt

sys.setrecursionlimit(1_000_000)
input = sys.stdin.readline

n, q = map(int, input().split())
a = list(map(int, input().split()))

size = 4 * n + 5
seg_sum = [0] * size
seg_min = [0] * size
seg_max = [0] * size
lazy = [0] * size
has_lazy = [0] * size


def build(node, left, right):
    if right - left == 1:
        value = a[left]
        seg_sum[node] = value
        seg_min[node] = value
        seg_max[node] = value
        lazy[node] = value
        has_lazy[node] = 1
        return
    mid = (left + right) >> 1
    build(node << 1, left, mid)
    build(node << 1 | 1, mid, right)
    pull(node)


def apply_set(node, left, right, value):
    seg_sum[node] = (right - left) * value
    seg_min[node] = value
    seg_max[node] = value
    lazy[node] = value
    has_lazy[node] = 1


def push(node, left, right):
    if not has_lazy[node] or right - left == 1:
        return
    mid = (left + right) >> 1
    value = lazy[node]
    apply_set(node << 1, left, mid, value)
    apply_set(node << 1 | 1, mid, right, value)
    has_lazy[node] = 0


def pull(node):
    left_node = node << 1
    right_node = left_node | 1
    seg_sum[node] = seg_sum[left_node] + seg_sum[right_node]
    seg_min[node] = seg_min[left_node] if seg_min[left_node] < seg_min[right_node] else seg_min[right_node]
    seg_max[node] = seg_max[left_node] if seg_max[left_node] > seg_max[right_node] else seg_max[right_node]


def range_assign(node, left, right, ql, qr, value):
    if qr <= left or right <= ql:
        return
    if ql <= left and right <= qr:
        apply_set(node, left, right, value)
        return
    push(node, left, right)
    mid = (left + right) >> 1
    range_assign(node << 1, left, mid, ql, qr, value)
    range_assign(node << 1 | 1, mid, right, ql, qr, value)
    pull(node)


def range_sqrt(node, left, right, ql, qr):
    if qr <= left or right <= ql or seg_max[node] <= 1:
        return

    if ql <= left and right <= qr:
        new_min = isqrt(seg_min[node])
        new_max = isqrt(seg_max[node])
        if new_min == new_max:
            apply_set(node, left, right, new_min)
            return
        if right - left == 1:
            apply_set(node, left, right, new_min)
            return

    push(node, left, right)
    mid = (left + right) >> 1
    range_sqrt(node << 1, left, mid, ql, qr)
    range_sqrt(node << 1 | 1, mid, right, ql, qr)
    pull(node)


def range_sum(node, left, right, ql, qr):
    if qr <= left or right <= ql:
        return 0
    if ql <= left and right <= qr:
        return seg_sum[node]
    push(node, left, right)
    mid = (left + right) >> 1
    return range_sum(node << 1, left, mid, ql, qr) + range_sum(node << 1 | 1, mid, right, ql, qr)


build(1, 0, n)
answer = []
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 0:
        answer.append(str(range_sum(1, 0, n, query[1], query[2])))
    elif query[0] == 1:
        range_assign(1, 0, n, query[1], query[2], query[3])
    else:
        range_sqrt(1, 0, n, query[1], query[2])

sys.stdout.write("\n".join(answer))
0