結果

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

ソースコード

diff #
raw source code 

import sys
from math import isqrt

def main():
    sys.setrecursionlimit(300000)
    d = sys.stdin.buffer.read().split(); i = 0
    N, Q = int(d[0]), int(d[1]); i = 2
    A = list(map(int, d[i:i+N])); i += N

    M = 1
    while M < N: M <<= 1
    S = [0]*(2*M); X = [0]*(2*M); T = [-1]*(2*M)   

    for k in range(N): S[M+k] = X[M+k] = T[M+k] = A[k]
    for k in range(M+N, 2*M): T[k] = 0
    for v in range(M-1, 0, -1):
        S[v] = S[2*v]+S[2*v+1]
        X[v] = max(X[2*v], X[2*v+1])
        T[v] = T[2*v] if T[2*v] != -1 and T[2*v] == T[2*v+1] else -1

    def put(v, n, x): S[v], X[v], T[v] = x*n, x, x
    def push(v, a, b):
        if T[v] != -1: put(2*v, a, T[v]); put(2*v+1, b, T[v]); T[v] = -1
    def pull(v):
        S[v] = S[2*v]+S[2*v+1]; X[v] = max(X[2*v], X[2*v+1])
        T[v] = T[2*v] if T[2*v] != -1 and T[2*v] == T[2*v+1] else -1

    def asn(v,l,r,ql,qr,x):
        if qr<=l or r<=ql: return
        if ql<=l and r<=qr: put(v,r-l,x); return
        m=(l+r)>>1; push(v,m-l,r-m)
        asn(2*v,l,m,ql,qr,x); asn(2*v+1,m,r,ql,qr,x); pull(v)

    def sqr(v,l,r,ql,qr):
        if qr<=l or r<=ql or X[v]<=1: return
        if ql<=l and r<=qr and T[v]!=-1: put(v,r-l,isqrt(T[v])); return
        m=(l+r)>>1; push(v,m-l,r-m)
        sqr(2*v,l,m,ql,qr); sqr(2*v+1,m,r,ql,qr); pull(v)

    def qs(v,l,r,ql,qr):
        if qr<=l or r<=ql: return 0
        if ql<=l and r<=qr: return S[v]
        m=(l+r)>>1; push(v,m-l,r-m)
        return qs(2*v,l,m,ql,qr)+qs(2*v+1,m,r,ql,qr)

    out = []
    for _ in range(Q):
        t = d[i]; i += 1
        if t == b'0':
            l,r = int(d[i]),int(d[i+1]); i+=2; out.append(str(qs(1,0,M,l,r)))
        elif t == b'1':
            l,r,x = int(d[i]),int(d[i+1]),int(d[i+2]); i+=3; asn(1,0,M,l,r,x)
        else:
            l,r = int(d[i]),int(d[i+1]); i+=2; sqr(1,0,M,l,r)
    sys.stdout.write('\n'.join(out))

main()
0