結果

問題 No.2942 Sigma Music Game Level Problem
コンテスト
ユーザー flippergo
提出日時 2025-02-13 10:49:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,005 ms / 6,000 ms
コード長 2,096 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 263,280 KB
最終ジャッジ日時 2025-02-13 10:49:58
合計ジャッジ時間 32,478 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

# セグメント木（点更新、区間和）:RSQ, BITでも実装可能
N,Q,L = map(int,input().split())
A = list(map(int,input().split()))
K = 0
while 2**K<2*10**5:
    K += 1
M = 2**K  # ノード数
T0 = [0]*(2*M)
T1 = [0]*(2*M)
R = [0]*(2*M)
for i in range(M,2*M):  # 0-origin
    R[i] = (i-M,i-M+1)
for i in range(M-1,0,-1):
    l1,r1 = R[2*i]
    l2,r2 = R[2*i+1]
    R[i] = (l1,r2)
def update0(i,x):  # １点更新
    i += M  # 頂点番号(0-origin)
    T0[i] += x
    i >>= 1  # 親に移る
    while i>0:
        T0[i] = T0[2*i]+T0[2*i+1]
        i >>= 1  # 親に移る
def update1(i,x):  # １点更新
    j = i
    i += M  # 頂点番号(0-origin)
    T1[i] += x*j
    i >>= 1  # 親に移る
    while i>0:
        T1[i] = T1[2*i]+T1[2*i+1]
        i >>= 1  # 親に移る
def find0(l,r):  # 区間取得
    l += M  # 頂点番号(0-origin)
    r += M  # 頂点番号(0-origin)
    result = 0
    while l<r:
        if l&1:  # lが奇数の場合（右の子）
            result += T0[l]
            l += 1  # 右隣に移動
        if r&1:  # rが奇数の場合（右の子）
            r -= 1  # 左隣に移動
            result += T0[r]
        l >>= 1  # 親に移動
        r >>= 1  # 親に移動
    return result
def find1(l,r):  # 区間取得
    l += M  # 頂点番号(0-origin)
    r += M  # 頂点番号(0-origin)
    result = 0
    while l<r:
        if l&1:  # lが奇数の場合（右の子）
            result += T1[l]
            l += 1  # 右隣に移動
        if r&1:  # rが奇数の場合（右の子）
            r -= 1  # 左隣に移動
            result += T1[r]
        l >>= 1  # 親に移動
        r >>= 1  # 親に移動
    return result
for i in range(N):
    update0(A[i],1)
    update1(A[i],1)
flag = True
for _ in range(Q):
    qry = list(map(int,input().split()))
    if qry[0]==1:
        a = qry[1]
        update0(a,1)
        update1(a,1)
    elif qry[0]==2:
        flag = False
        l,r = qry[1:]
        r += 1
        print(find0(l,r),find1(l,r))
    else:
        L = qry[1]
if flag:
    print("Not Found!")
0