結果

問題 No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー titia
提出日時 2026-06-17 08:03:07
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 3,447 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 139 ms
コンパイル使用メモリ 85,564 KB
実行使用メモリ 94,264 KB
最終ジャッジ日時 2026-06-17 08:04:06
合計ジャッジ時間 17,759 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 11 TLE * 2 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

N,Q=list(map(int,input().split()))
A=list(map(int,input().split()))

sq=int(N**(1/2))
LEN=(N+sq-1)//sq
lastLEN=N%sq
UNIT=[-1]*LEN
SUM=[0]*LEN
for i in range(LEN):
    LIST=[]
    for j in range(i*sq,min(N,i*sq+sq)):
        LIST.append(A[j])
        SUM[i]+=A[j]

    #print(LIST)
        
    if len(set(LIST))==1:
        UNIT[i]=LIST[0]

for tests in range(Q):
    #print(A)
    L=list(map(int,input().split()))

    if L[0]==0:
        l,r=L[1],L[2]
        ANS=0

        now=l
        while now<r and now%sq!=0:
            if UNIT[now//sq]!=-1:
                ANS+=UNIT[now//sq]
            else:
                ANS+=A[now]
            now+=1

        while now<r and now+sq<r:
            ANS+=SUM[now//sq]
            now+=sq

        while now<r:
            if UNIT[now//sq]!=-1:
                ANS+=UNIT[now//sq]
            else:
                ANS+=A[now]
            now+=1

        print(ANS)

    elif L[0]==1:
        l,r,x=L[1:]

        now=l
        while now<r and now%sq!=0:
            if UNIT[now//sq]!=-1:
                ume=UNIT[now//sq]
                UNIT[now//sq]=-1
                SUM[now//sq]=0

                for i in range(now//sq*sq,min(N,now//sq*sq+sq)):
                    A[i]=ume
                    SUM[now//sq]+=A[i]

            SUM[now//sq]-=A[now]
            A[now]=x
            SUM[now//sq]+=A[now]
            now+=1

        while now<r and now+sq<r:
            UNIT[now//sq]=x
            SUM[now//sq]=x*sq
            now+=sq

        while now<r:
            if UNIT[now//sq]!=-1:
                ume=UNIT[now//sq]
                UNIT[now//sq]=-1
                SUM[now//sq]=0

                for i in range(now//sq*sq,min(N,now//sq*sq+sq)):
                    A[i]=ume
                    SUM[now//sq]+=A[i]

            SUM[now//sq]-=A[now]
            A[now]=x
            SUM[now//sq]+=A[now]
            now+=1

    elif L[0]==2:
        l,r=L[1],L[2]

        now=l
        while now<r and now%sq!=0:
            if UNIT[now//sq]!=-1:
                ume=UNIT[now//sq]
                UNIT[now//sq]=-1
                SUM[now//sq]=0

                for i in range(now//sq*sq,min(N,now//sq*sq+sq)):
                    A[i]=ume
                    SUM[now//sq]+=A[i]

            SUM[now//sq]-=A[now]
            A[now]=int(A[now]**(1/2))
            SUM[now//sq]+=A[now]
            now+=1

        while now<r and now+sq<r:
            if UNIT[now//sq]!=-1:
                ume=int(UNIT[now//sq]**(1/2))
                UNIT[now//sq]=ume
                SUM[now//sq]=ume*sq
                now+=sq
            else:
                LIST=[]
                SUM[now//sq]=0
                for i in range(now,now+sq):
                    A[i]=int(A[i]**(1/2))
                    SUM[now//sq]+=A[i]
                    LIST.append(A[i])

                if len(set(LIST))==1:
                    UNIT[now//sq]=LIST[0]
                    SUM[now//sq]=LIST[0]*sq
                now+=sq
        while now<r:
            if UNIT[now//sq]!=-1:
                ume=UNIT[now//sq]
                UNIT[now//sq]=-1
                SUM[now//sq]=0

                for i in range(now//sq*sq,min(N,now//sq*sq+sq)):
                    A[i]=ume
                    SUM[now//sq]+=A[i]

            SUM[now//sq]-=A[now]
            A[now]=int(A[now]**(1/2))
            SUM[now//sq]+=A[now]
            now+=1
0