結果

問題 No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー titia
提出日時 2026-06-17 08:08:22
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 3,686 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 407 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 95,448 KB
最終ジャッジ日時 2026-06-17 08:09:35
合計ジャッジ時間 16,809 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 12 TLE * 1 -- * 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):
    one=-1
    for j in range(i*sq,min(N,i*sq+sq)):
        if one==-1:
            one=A[j]
        elif one==A[j]:
            pass
        else:
            one=-2
        SUM[i]+=A[j]

    #print(LIST)
        
    if one>=0:
        UNIT[i]=one

LANS=[]
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

        LANS.append(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:
                one=-1
                SUM[now//sq]=0
                for i in range(now,now+sq):
                    A[i]=int(A[i]**(1/2))
                    SUM[now//sq]+=A[i]
                    if one==-1:
                        one=A[i]
                    elif one==A[i]:
                        pass
                    else:
                        one=-2

                if one>=0:
                    UNIT[now//sq]=one
                    SUM[now//sq]=one*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

        
        
print("\n".join(map(str,LANS)))
0