Problem p03641 (python)

Fixed submission:
import sys
input = sys.stdin.readline

# O(NlogN)構築、クエリO(1)のRMQ
# 変更はできない
class SparseTable():
    def __init__(self, N, A):
        self.N = N
        self.logN = N.bit_length()
        self.A = A
        self.table = [[i for i in range(N)]]
        for k in range(self.logN):
            tab = []
            for i in range(self.N-(1<<(k+1))+1):
                ind1 = self.table[-1][i]
                ind2 = self.table[-1][i+(1<<k)]
                if self.A[ind1] <= self.A[ind2]:
                    tab.append(ind1)
                else:
                    tab.append(ind2)
            self.table.append(tab)
    
    # [l, r)のminの(val, key)
    def query_min(self, l, r):
        k = (r-l).bit_length()-1
        indl = self.table[k][l]
        indr = self.table[k][r-(1<<k)]
        if self.A[indl] <= self.A[indr]:
            return self.A[indl], indl
        return self.A[indr], indr

import heapq as hp
N = int(input())
A = list(map(int, input().split()))

def main():
    SP1 = SparseTable((N+1)//2, A[::2])
    SP2 = SparseTable(N//2, A[1::2])

    ans = []
    q = []
    v, k = SP1.query_min(0, N//2)
    dic = {}
    dic[v] = (k, 0, N//2, True)
    hp.heappush(q, v)
    for _ in range(N//2):
        valuea = hp.heappop(q)
        ka, l, r, is1 = dic[valuea]
        ans.append(str(valuea))
        if is1:
            valueb, kb = SP2.query_min(ka, r)
            if ka < kb:
                m2, nk2 = SP2.query_min(ka, kb)
                hp.heappush(q, m2)
                dic[m2] = (nk2, ka, kb+1, False)
            if l < ka:
                m1, nk1 = SP1.query_min(l, ka)
                hp.heappush(q, m1)
                dic[m1] = (nk1, l, ka, True)
            if kb+1 < r:
                m3, nk3 = SP1.query_min(kb+1, r)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb+1, r, True)
        else:
            valueb, kb = SP1.query_min(ka+1, r)
            if ka+1 < kb:
                m1, nk1 = SP1.query_min(ka+1, kb)
                hp.heappush(q, m1)
                dic[m1] = (nk1, ka+1, kb, True)
            if l < ka:
                m2, nk2 = SP2.query_min(l, ka)
                hp.heappush(q, m2)
                dic[m2] = (nk2, l, ka+1, False)
            if kb < r-1:
                m3, nk3 = SP2.query_min(kb, r-1)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb, r, False)

        ans.append(str(valueb))

    print(" ".join(ans))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# AOJ DSL_2_A "Range Minimum Query"
# SegmantTreeの実装
import sys
input = sys.stdin.readline

# 初期化最大値
INF = (1 << 31) - 1

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [[INF, -1] for _ in range(2*self.N-1)]

    # k番目の値(0-indexed)をaに変更
    def update(self, k, a):
        self.data[k+self.N-1] = [a, k]
        k += self.N - 1
        while k > 0:
            k = (k-1)//2
            if self.data[2*k+1][0] < self.data[2*k+2][0]:
                self.data[k] = self.data[2*k+1][:]
            else:
                self.data[k] = self.data[2*k+2][:]

    # [l, r)の最小値取得
    # kがNodeの番号、対応する区間が[a, b)
    def query_min(self, l, r):
        L = l + self.N
        R = r + self.N
        s = [INF, -1]
        while L < R:
            if R & 1:
                R -= 1
                if s[0] > self.data[R-1][0]:
                    s = self.data[R-1]
            if L & 1:
                if s[0] > self.data[L-1][0]:
                    s = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

import heapq as hp
N = int(input())
A = list(map(int, input().split()))

ST1 = SegmentTree(N//2)
ST2 = SegmentTree(N//2)
for i,a in enumerate(A):
    if i%2==0:
        ST1.update(i//2, a)
    else:
        ST2.update(i//2, a)

ans = []
q = []
v, k = ST1.query_min(0, N//2)
hp.heappush(q, (v, k, 0, N//2, True))
for _ in range(N//2):
    valuea, ka, l, r, is1 = hp.heappop(q)
    ans.append(valuea)
    if is1:
        valueb, kb = ST2.query_min(ka, r)
        if ka < kb:
            m2, nk2 = ST2.query_min(ka, kb)
            hp.heappush(q, (m2, nk2, ka, kb+1, False))
        if l < ka:
            m1, nk1 = ST1.query_min(l, ka)
            hp.heappush(q, (m1, nk1, l, ka, True))
        if kb+1 < r:
            m3, nk3 = ST1.query_min(kb+1, r)
            hp.heappush(q, (m3, nk3, kb+1, r, True))
    else:
        valueb, kb = ST1.query_min(ka+1, r)
        if ka+1 < kb:
            m1, nk1 = ST1.query_min(ka+1, kb)
            hp.heappush(q, (m1, nk1, ka+1, kb, True))
        if l < ka:
            m2, nk2 = ST2.query_min(l, ka)
            hp.heappush(q, (m2, nk2, l, ka, False))
        if kb < r-1:
            m3, nk3 = ST2.query_min(kb, r-1)
            hp.heappush(q, (m3, nk3, kb, r-1, False))

    ans.append(valueb)

print(*ans)