結果

問題 No.1441 MErGe
コンテスト
ユーザー H3PO4
提出日時 2021-03-26 23:06:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,066 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 132,612 KB
最終ジャッジ日時 2024-11-29 01:16:59
合計ジャッジ時間 21,167 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 WA * 17 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import random
import sys
import itertools

input = sys.stdin.buffer.readline

random.seed()


class RBST:
    """https://tjkendev.github.io/procon-library/python/binary_search_tree/RBST.html から拝借しています。"""

    def __init__(self):
        self.root = None

    # find a node with a key x
    def find(self, x):
        node = self.root
        while node:
            v = node[2]
            if v == x:
                return 1
            node = node[v < x]
        return 0

    # find the k-th key in a tree
    def at(self, k):
        node = self.root
        k += 1
        while 1:
            v = (node[0][3] + 1 if node[0] else 1)
            if v == k:
                return node[2]
            if k < v:
                node = node[0]
            else:
                k -= v
                node = node[1]
        return -1

    # insert a node with a key x
    def insert(self, x):
        # before insert(x), the tree must not contain a key x
        rand = random.random
        new_node = [None, None, x, 1]
        if not self.root:
            self.root = new_node
            return
        node = self.root
        prv = None
        while node:
            if node[3] == int(rand() * (node[3] + 1)):
                break
            node[3] += 1
            prv = node
            node = node[node[2] < x]
        if prv:
            prv[prv[2] < x] = new_node
        else:
            self.root = new_node

        left = right = new_node
        st = []
        while node:
            st.append(node)
            if node[2] < x:
                left[1] = left = node
                node = node[1]
            else:
                right[0] = right = node
                node = node[0]
        left[1] = right[0] = None
        new_node[0], new_node[1] = new_node[1], new_node[0]

        st.reverse()
        for node in st:
            l, r = node[:2]
            node[3] = (l[3] if l else 0) + (r[3] if r else 0) + 1
        l, r = new_node[:2]
        new_node[3] = (l[3] if l else 0) + (r[3] if r else 0) + 1

    # remove a node with key x
    def remove(self, x):
        # before remove(x), the tree must contain a key x
        rand = random.random
        node = self.root
        prt = None
        while node[2] != x:
            node[3] -= 1
            prt = node
            node = node[node[2] < x]

        cur = top = prt
        if prt:
            prv_d = (prt[1] == node)
        else:
            cur = top = [None]
            prv_d = 0
        left, right = node[:2]
        st = [];
        push = st.append
        while left and right:
            a = left[3];
            b = right[3]
            if int(rand() * (a + b)) < a:
                push(left)
                cur[prv_d] = cur = left
                left = left[1]
                prv_d = 1
            else:
                push(right)
                cur[prv_d] = cur = right
                right = right[0]
                prv_d = 0
        rest = left or right
        cur[prv_d] = rest
        if not prt:
            self.root = top[0]

        st.reverse()
        for node in st:
            l, r = node[:2]
            node[3] = (l[3] if l else 0) + (r[3] if r else 0) + 1

    # pop the k-th key
    def pop(self, k):
        # when pop(x), the tree should contain the k-th element
        rand = random.random
        node = self.root
        prt = None
        k += 1
        while 1:
            l = node[0]
            v = (l[3] + 1 if l else 1)
            if v == k:
                break
            prt = node
            node[3] -= 1
            if k < v:
                node = node[0]
            else:
                k -= v
                node = node[1]
        r_node = node

        cur = top = prt
        if prt:
            prv_d = (prt[1] == node)
        else:
            cur = top = [None]
            prv_d = 0
        left, right = node[:2]
        st = [];
        push = st.append
        while left and right:
            a = left[3];
            b = right[3]
            if int(rand() * (a + b)) < a:
                push(left)
                cur[prv_d] = cur = left
                left = left[1]
                prv_d = 1
            else:
                push(right)
                cur[prv_d] = cur = right
                right = right[0]
                prv_d = 0
        rest = left or right
        cur[prv_d] = rest
        if not prt:
            self.root = top[0]

        st.reverse()
        for node in st:
            l, r = node[:2]
            node[3] = (l[3] if l else 0) + (r[3] if r else 0) + 1

        return r_node[2]


N, Q = map(int, input().split())
A = tuple(map(int, input().split()))
As = [0] + list(itertools.accumulate(A))
indices = RBST()
for i in range(N):
    indices.insert(i)
for _ in range(Q):
    t, l, r = map(int, input().split())
    l -= 1
    r -= 1
    if t == 1:
        for i in range(r - l):
            x = indices.pop(l + 1)
    else:  # t==2
        lidx = indices.at(l)
        ridx = indices.at(r)
        print(As[ridx + 1] - As[lidx])
0