Problem p03641 (python)

Fixed submission:
import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx

N = int(readline())

inf = 1<<32
P = list(map(int, readline().split()))

Pi = [None]*(N+1)
for i in range(N):
    Pi[P[i]] = i

inf = 1<<32
Peven = [P[i] if not i&1 else inf for i in range(N)]
Podd = [P[i] if i&1 else inf for i in range(N)]

Teven = Segtree(Peven, inf, initialize = True, segf = min)
Todd = Segtree(Podd, inf, initialize = True, segf = min)
N0 = 2**(N-1).bit_length()

Q = [(Teven.query(0, N0), 0, N0)]
for i in range(N//2):
    t1, l, r = hpp(Q)
    K = []
    if not l&1:
        p1 = Pi[t1]
        t2 = Todd.query(p1, r)
        p2 = Pi[t2]
        Teven.update(p1, inf)
        Todd.update(p2, inf)
    else:
        p1 = Pi[t1]
        t2 = Teven.query(p1, r)
        p2 = Pi[t2]
        Todd.update(p1, inf)
        Teven.update(p2, inf)
    if l < p1:
        K.append((l, p1))
    if p2 < r:
        K.append((p2+1, r))
    if p1 + 1 < p2:
        K.append((p1+1, p2))
    for l, r in K:
        if not l&1:
            mq = Teven.query(l, r)
        else:
            mq = Todd.query(l, r)
        hp(Q, (mq, l, r))
    sys.stdout.write('{} {} '.format(t1, t2))
sys.stdout.write('\n')

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx

N = int(readline())

inf = 1<<32
P = list(map(int, readline().split()))

Pi = [None]*(N+1)
for i in range(N):
    Pi[P[i]] = i

inf = 1<<32
Peven = [P[i] if not i&1 else inf for i in range(N)]
Podd = [P[i] if i&1 else inf for i in range(N)]

Teven = Segtree(Peven, inf, initialize = True, segf = min)
Todd = Segtree(Podd, inf, initialize = True, segf = min)
N0 = 2**(N-1).bit_length()

Q = [(Teven.query(0, N0), 0, N0)]
for i in range(N//2):
    t1, l, r = hpp(Q)
    K = []
    if not l&1:
        p1 = Pi[t1]
        t2 = Todd.query(l, r)
        p2 = Pi[t2]
        Teven.update(p1, inf)
        Todd.update(p2, inf)
    else:
        p1 = Pi[t1]
        t2 = Teven.query(l, r)
        p2 = Pi[t2]
        Todd.update(p1, inf)
        Teven.update(p2, inf)
    if l < p1:
        K.append((l, p1))
    if p2 < r:
        K.append((p2+1, r))
    if p1 + 1 < p2:
        K.append((p1+1, p2))
    for l, r in K:
        if not l&1:
            mq = Teven.query(l, r)
        else:
            mq = Todd.query(l, r)
        hp(Q, (mq, l, r))
    sys.stdout.write('{} {} '.format(t1, t2))
sys.stdout.write('\n')

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
class Dualsegtree:
    def __init__(self, A, intv, initialize = True):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = min
        if initialize:
            self.data = [intv]*(self.N0-1) + A + [intv]*(self.N0 - self.N + 1)
            for i in range(self.N0-2, -1, -1):
                self.data[i] = self.segf(self.data[2*i+1], self.data[2*i+2]) 
        else:
            self.data = [intv]*(2*self.N0)
                
    def query(self, k):
        k += self.N0-1
        s = self.data[k]
        while k >= 0 :
            k = (k-1) >> 1
            s = self.segf(s, self.data[k])
        return s
    
    def update(self, l, r, x):
        L, R = l+self.N0, r+self.N0
        while L < R:
            if R & 1:
                R -= 1
                self.data[R-1] = self.segf(self.data[R-1], x)
            if L & 1:
                self.data[L-1] = self.segf(self.data[L-1], x)
                L += 1
            L >>= 1
            R >>= 1
        
class Lazysegtree:
    def __init__(self, A):
        #区間は 1-indexed で管理
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv1 = inf
        self.intv2 = -inf
        self.segf1 = min
        self.segf2 = max
        self.lazy = [1]*(2*self.N0)
        self.data1 = [self.intv1]*self.N0 + A + [self.intv1]*(self.N0 - self.N)
        for i in range(self.N0-1, 0, -1):
            self.data1[i] = self.segf1(self.data1[2*i], self.data1[2*i+1]) 
        self.data2 = [self.intv2]*self.N0 + A + [self.intv2]*(self.N0 - self.N)
        for i in range(self.N0-1, 0, -1):
            self.data2[i] = self.segf2(self.data2[2*i], self.data2[2*i+1]) 
       
    def _ascend(self, k):
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data1[idx] = self.segf1(self.data1[2*idx], self.data1[2*idx+1])
            self.data2[idx] = self.segf2(self.data2[2*idx], self.data2[2*idx+1])
            
    def _descend(self, k):
        k = k >> 1
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            ax = self.lazy[idx]
            if ax == 1:
                continue
            self.lazy[idx] = 1
            self.data1[2*idx], self.data2[2*idx] = -self.data2[2*idx], -self.data1[2*idx]
            self.data1[2*idx+1], self.data2[2*idx+1] = -self.data2[2*idx+1], -self.data1[2*idx+1]
            self.lazy[2*idx] *= ax
            self.lazy[2*idx+1] *= ax
    
    def query(self, l, r):
        L = l+self.N0
        R = r+self.N0
        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri - 1)
        
        s1 = self.intv1
        s2 = self.intv2                                                              
        while L < R:
            if R & 1:
                R -= 1
                s1 = self.segf1(s1, self.data1[R])
                s2 = self.segf2(s2, self.data2[R])

            if L & 1:
                s1 = self.segf1(s1, self.data1[L])
                s2 = self.segf2(s2, self.data2[L])
                L += 1
            L >>= 1
            R >>= 1
        return (s1, s2)
    
    def update(self, i, x):
        idx = i+self.N0
        self.data1[idx] = x
        self.data2[idx] = x
        self._ascend(idx)
        
    def updaterange(self, l, r, x):
        L = l+self.N0
        R = r+self.N0

        Li = L//(L & -L)
        Ri = R//(R & -R)
        
        while L < R :
            if R & 1:
                R -= 1
                self.data1[R], self.data2[R] = -self.data2[R], -self.data1[R]
                self.lazy[R] *= x
            if L & 1:
                self.data1[L], self.data2[L] = -self.data2[L], -self.data1[L]
                self.lazy[L] *= x
                L += 1
            L >>= 1
            R >>= 1
        
        self._ascend(Li)
        self._ascend(Ri-1)

N = int(readline())

inf = 1<<32
P = list(map(int, readline().split()))

Pi = [None]*(N+1)
for i in range(N):
    Pi[P[i]] = i

T = Lazysegtree([(N+1 - P[i])*(-1)**i for i in range(N)])
N0 = 2**(N-1).bit_length()

R = Dualsegtree([N0]*N, N0, initialize = True)
for i in range(N//2):
    _, t2 = T.query(0, N0)
    t2 = N+1-abs(t2)
    p2 = Pi[t2]
    t1, _ = T.query(p2, R.query(p2))
    t1 = N+1-abs(t1)
    p1 = Pi[t1]
    
    if p1 > p2:
        p1, p2 = p2, p1
    T.update(p1, 0)
    T.update(p2, 0)
    T.updaterange(p1+1, p2, -1)
    R.update(0, p1, p1)
    R.update(0, p2, p2)
    
    sys.stdout.write('{} {} '.format(t2, t1))
sys.stdout.write('\n')