結果

問題 No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー ,
提出日時 2026-04-19 12:31:46
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 3,731 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 542 ms
コンパイル使用メモリ 20,828 KB
実行使用メモリ 52,140 KB
最終ジャッジ日時 2026-04-19 12:39:24
合計ジャッジ時間 13,508 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 3 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from math import isqrt

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0

    n, q = int(data[idx]), int(data[idx+1]); idx += 2
    A = [int(data[idx+i]) for i in range(n)]; idx += n

    size = 1
    while size < n:
        size <<= 1

    INF = -1
    sm   = [0]   * (2 * size)
    mn   = [0]   * (2 * size)
    mx   = [0]   * (2 * size)
    lazy = [INF] * (2 * size)

    for i in range(n):
        sm[size+i] = mn[size+i] = mx[size+i] = A[i]
    for i in range(size-1, 0, -1):
        sm[i] = sm[2*i] + sm[2*i+1]
        mn[i] = min(mn[2*i], mn[2*i+1])
        mx[i] = max(mx[2*i], mx[2*i+1])

    def apply_node(v, l, r, val):
        sm[v] = val * (r - l)
        mn[v] = val
        mx[v] = val
        lazy[v] = val

    def push(v, l, r):
        if lazy[v] != INF:
            mid = (l + r) >> 1
            apply_node(2*v,   l,   mid, lazy[v])
            apply_node(2*v+1, mid, r,   lazy[v])
            lazy[v] = INF

    def pull(v):
        sm[v] = sm[2*v] + sm[2*v+1]
        mn[v] = min(mn[2*v], mn[2*v+1])
        mx[v] = max(mx[2*v], mx[2*v+1])

    def node_range(v):
        depth = v.bit_length() - 1
        seg_size = size >> depth
        pos = v - (1 << depth)
        return pos * seg_size, pos * seg_size + seg_size

    def push_path(ql, qr):
        nodes = []
        lo, hi = ql + size, qr + size
        lo >>= 1; hi = (hi-1) >> 1
        while lo > 0:
            nodes.append(lo)
            nodes.append(hi)
            lo >>= 1; hi >>= 1
        for v in reversed(nodes):
            l, r = node_range(v)
            push(v, l, r)

    def query_sum(ql, qr):
        push_path(ql, qr)
        res = 0
        l, r = ql + size, qr + size
        while l < r:
            if l & 1: res += sm[l]; l += 1
            if r & 1: r -= 1; res += sm[r]
            l >>= 1; r >>= 1
        return res

    def update_assign(ql, qr, val):
        push_path(ql, qr)
        l, r = ql + size, qr + size
        l0, r0 = l, r
        while l < r:
            if l & 1:
                nl, nr = node_range(l)
                apply_node(l, nl, nr, val); l += 1
            if r & 1:
                r -= 1
                nl, nr = node_range(r)
                apply_node(r, nl, nr, val)
            l >>= 1; r >>= 1
        l, r = l0 >> 1, (r0-1) >> 1
        while l > 0:
            if lazy[l] == INF: pull(l)
            if lazy[r] == INF: pull(r)
            l >>= 1; r >>= 1

    def update_isqrt_range(ql, qr):
        stack = [(1, 0, size, False)]
        while stack:
            v, l, r, returning = stack.pop()
            if returning:
                pull(v)
                continue
            if ql >= r or l >= qr:
                continue
            sq_mn = isqrt(mn[v])
            sq_mx = isqrt(mx[v])
            if ql <= l and r <= qr and sq_mn == sq_mx:
                apply_node(v, l, r, sq_mn)
                continue
            if l + 1 == r:
                sm[v] = mn[v] = mx[v] = sq_mn
                lazy[v] = INF
                continue
            push(v, l, r)
            mid = (l + r) >> 1
            stack.append((v, l, r, True))
            stack.append((2*v+1, mid, r, False))
            stack.append((2*v,   l, mid, False))

    out = []
    for _ in range(q):
        t = int(data[idx]); idx += 1
        if t == 0:
            l, r = int(data[idx]), int(data[idx+1]); idx += 2
            out.append(query_sum(l, r))
        elif t == 1:
            l, r, x = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
            update_assign(l, r, x)
        else:
            l, r = int(data[idx]), int(data[idx+1]); idx += 2
            update_isqrt_range(l, r)

    sys.stdout.write('\n'.join(map(str, out)) + '\n')

main()
0