結果

問題 No.1099 Range Square Sum
コンテスト
ユーザー titia
提出日時 2026-03-09 07:21:28
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,169 ms / 2,000 ms
コード長 4,006 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 256 ms
コンパイル使用メモリ 85,704 KB
実行使用メモリ 138,644 KB
最終ジャッジ日時 2026-03-09 07:21:46
合計ジャッジ時間 13,716 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

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

# 非再帰遅延伝搬セグ木（範囲更新, 範囲和出力）
# 高々N点を更新

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
seg_height=1+N.bit_length() # Segment treeのたかさ
SEG=[[0,0] for i in range(2*seg_el)] # sum,xy+yz+zx
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R): # 遅延伝搬すべきノードのリストを返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST

def adds(l,r,x): # 区間[l,r)を+x
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=0:
            #print("!",ind,seg_height  - ((ind<<1).bit_length()))
            update_lazy = LAZY[ind]
            LAZY[ind<<1]+=update_lazy
            LAZY[1+(ind<<1)]+=update_lazy
            ko=(1<<(seg_height  - ((ind<<1).bit_length())))
            SEG[ind<<1][1]+=(ko-1)*update_lazy*SEG[ind<<1][0]+update_lazy*update_lazy*ko*(ko-1)//2
            SEG[ind<<1][0]+=update_lazy*ko

            SEG[1+(ind<<1)][1]+=(ko-1)*update_lazy*SEG[1+(ind<<1)][0]+update_lazy*update_lazy*ko*(ko-1)//2
            SEG[1+(ind<<1)][0]+=update_lazy*ko

            LAZY[ind]=0

    while L!=R:
        if L > R:
            ko=(1<<(seg_height - (L.bit_length())))
            #print(L,ko)
            SEG[L][1]+=(ko-1)*x * SEG[L][0] + x*x*ko*(ko-1)//2
            SEG[L][0]+=x * ko
            #print(SEG[L])

            
            LAZY[L]+=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ko=(1<<(seg_height - (R.bit_length())))
            SEG[R][1]+=(ko-1)*x * SEG[R][0]+ x*x*ko*(ko-1)//2
            SEG[R][0]+=x * ko
            
            LAZY[R]+=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind][0]=SEG[ind<<1][0]+SEG[1+(ind<<1)][0]
        SEG[ind][1]=SEG[ind<<1][1]+SEG[1+(ind<<1)][1]+SEG[ind<<1][0]*SEG[1+(ind<<1)][0]

def getvalues(l,r): # 区間[l,r)に関する和を調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=0:
            #print("!",ind,seg_height  - ((ind<<1).bit_length()))
            update_lazy = LAZY[ind]
            LAZY[ind<<1]+=update_lazy
            LAZY[1+(ind<<1)]+=update_lazy
            ko=(1<<(seg_height  - ((ind<<1).bit_length())))
            SEG[ind<<1][1]+=(ko-1)*update_lazy*SEG[ind<<1][0]+update_lazy*update_lazy*ko*(ko-1)//2
            SEG[ind<<1][0]+=update_lazy*ko

            SEG[1+(ind<<1)][1]+=(ko-1)*update_lazy*SEG[1+(ind<<1)][0]+update_lazy*update_lazy*ko*(ko-1)//2
            SEG[1+(ind<<1)][0]+=update_lazy*ko

            LAZY[ind]=0
            
    ANS0=0
    ANS1=0

    while L!=R:
        #print(ANS0,ANS1)
        if L > R:
            ANS1=ANS1+SEG[L][1]+ANS0*SEG[L][0]
            ANS0=ANS0+SEG[L][0]
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS1=ANS1+SEG[R][1]+ANS0*SEG[R][0]
            ANS0=ANS0+SEG[R][0]
            R//=(R & (-R))

    return ANS0,ANS1

for i in range(N):
    adds(i,i+1,A[i])


        

Q=int(input())

for tests in range(Q):
    #print(SEG)
    #for i in range(N):
    #    for j in range(i,N+1):
    #        score=getvalues(i,j)
    #        print(i,j,score)
    #print()
    L=list(map(int,input().split()))

    if L[0]==1:
        l,r,x=L[1:]
        adds(l-1,r,x)
    else:
        l,r=L[1:]

        ANS0,ANS1=getvalues(l-1,r)

        #print("!!!",ANS0,ANS1)
        print(ANS0*ANS0-2*ANS1)
0