結果

問題 No.1441 MErGe
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:27:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,555 bytes
コンパイル時間 284 ms
コンパイル使用メモリ 82,012 KB
実行使用メモリ 162,772 KB
最終ジャッジ日時 2025-06-12 21:29:01
合計ジャッジ時間 13,752 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 TLE * 4 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import random
sys.setrecursionlimit(1 << 25)

class Node:
    def __init__(self, own_sum, own_size):
        self.own_sum = own_sum
        self.own_size = own_size
        self.sum = own_sum
        self.size = own_size
        self.priority = random.randint(0, 10**18)
        self.left = None
        self.right = None

def get_size(node):
    return node.size if node is not None else 0

def get_sum(node):
    return node.sum if node is not None else 0

def update(node):
    if node is None:
        return
    node.size = node.own_size + get_size(node.left) + get_size(node.right)
    node.sum = node.own_sum + get_sum(node.left) + get_sum(node.right)

def split(node, key):
    if node is None:
        return (None, None)
    left_size = get_size(node.left)
    if key <= left_size:
        left, right = split(node.left, key)
        node.left = right
        update(node)
        return (left, node)
    else:
        left, right = split(node.right, key - left_size - node.own_size)
        node.right = left
        update(node)
        return (node, right)

def merge(left, right):
    if left is None:
        return right
    if right is None:
        return left
    if left.priority > right.priority:
        left.right = merge(left.right, right)
        update(left)
        return left
    else:
        right.left = merge(left, right.left)
        update(right)
        return right

def build_treap(arr):
    if not arr:
        return None
    mid = len(arr) // 2
    node = Node(arr[mid], 1)
    node.left = build_treap(arr[:mid])
    node.right = build_treap(arr[mid+1:])
    update(node)
    return node

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    treap = build_treap(A)
    for _ in range(Q):
        T = int(input[ptr])
        ptr += 1
        l = int(input[ptr])
        ptr += 1
        r = int(input[ptr])
        ptr += 1
        if T == 1:
            left1, right1 = split(treap, l-1)
            middle, right2 = split(right1, r - l + 1)
            sum_middle = get_sum(middle)
            new_node = Node(sum_middle, 1)
            treap = merge(left1, merge(new_node, right2))
        else:
            left1, right1 = split(treap, l-1)
            middle, right2 = split(right1, r - l + 1)
            sum_middle = get_sum(middle)
            print(sum_middle)
            treap = merge(left1, merge(middle, right2))

if __name__ == "__main__":
    main()
0