結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー titia
提出日時 2025-09-18 04:19:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,681 ms / 2,500 ms
コード長 2,498 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 151,980 KB
最終ジャッジ日時 2025-09-18 04:20:40
合計ジャッジ時間 43,656 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N,M=map(int,input().split())

seg_el=1<<((M+100).bit_length())

SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def seg_function(x,y):
    return x+y

def update(n,x,seg_el): # A[n]をxへ更新
    i=n+seg_el
    SEG[i]=x
    i>>=1 # 子ノードへ
    
    while i!=0:
        SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べる
    L=l+seg_el
    R=r+seg_el
    ANS1=0
    ANS2=0

    while L<R:
        if L & 1:
            ANS1=seg_function(ANS1, SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS2=seg_function(SEG[R], ANS2)
        L>>=1
        R>>=1

    return seg_function(ANS1, ANS2)

def getvalue(n,seg_el): # 一点の値を取得
    i=n+seg_el
    ANS=0
    
    ANS=SEG[i]
    i>>=1# 子ノードへ
    
    while i!=0:
        ANS+=SEG[i]
        i>>=1

    return ANS

def updates(l,r,x): # 区間[l,r)を+x更新.
    L=l+seg_el
    R=r+seg_el

    while L<R:
        if L & 1:
            SEG[L]+=x
            L+=1

        if R & 1:
            R-=1
            SEG[R]+=x
        L>>=1
        R>>=1

SEG2=[0]*(2*seg_el)

def getvalue2(n,seg_el): # 一点の値を取得
    i=n+seg_el
    ANS=0
    
    ANS=SEG2[i]
    i>>=1# 子ノードへ
    
    while i!=0:
        ANS+=SEG2[i]
        i>>=1

    return ANS

def updates2(l,r,x): # 区間[l,r)を+x更新.
    L=l+seg_el
    R=r+seg_el

    while L<R:
        if L & 1:
            SEG2[L]+=x
            L+=1

        if R & 1:
            R-=1
            SEG2[R]+=x
        L>>=1
        R>>=1

ANS=0
X=[[] for i in range(N+1)]
for i in range(N):
    a,l,r=map(int,input().split())
    update(i+1,a,seg_el)
    updates2(l,r+1,1)
    ANS+=a*(r-l+1)

    X[i+1]=(a,i+1,l,r)

for i in range(N+1):
    if X[i]==[]:
        continue
    a,p,l,r=X[i]
    k=getvalue2(p,seg_el)
    ANS-=k*a

#print(ANS)

Q=int(input())

for tests in range(Q):
    x,y,u,v=map(int,input().split())

    a,p,l,r=X[x]

    ANS+=getvalue2(p,seg_el)*a

    #print(ANS)
    ANS-=a*(r-l+1)

    #print(ANS)
    update(p,0,seg_el)
    updates2(l,r+1,-1)

    ANS+=getvalues(l,r+1)

    #print(ANS)

    #updates2(l,r+1,-1)

    X[x]=(a,y,u,v)

    ANS+=a*(v-u+1)

    #print(ANS)

    ANS-=getvalue2(y,seg_el)*a
    
    updates2(u,v+1,1)
    update(y,a,seg_el)
    ANS-=getvalues(u,v+1)
    

    update(y,a,seg_el)

    print(ANS)
0