Problem:


Score : 800 points

Problem Statement

Let N be a positive even number.

We have a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N).
Snuke is constructing another permutation of (1, 2, ..., N), q, following the procedure below.

First, let q be an empty sequence.
Then, perform the following operation until p becomes empty:

Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.

When p becomes empty, q will be a permutation of (1, 2, ..., N).

Find the lexicographically smallest permutation that can be obtained as q.

Constraints

N is an even number.

2 ≤ N ≤ 2 × 10^5

p is a permutation of (1, 2, ..., N).

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 ... p_N

Output

Print the lexicographically smallest permutation, with spaces in between.

Sample Input 1

4
3 2 4 1

Sample Output 1

3 1 2 4

The solution above is obtained as follows:

p
q

(3, 2, 4, 1)
()

↓
↓

(3, 1)
(2, 4)

↓
↓

()
(3, 1, 2, 4)

Sample Input 2

2
1 2

Sample Output 2

1 2

Sample Input 3

8
4 6 3 2 8 5 7 1

Sample Output 3

3 1 2 7 4 6 8 5

The solution above is obtained as follows:

p
q

(4, 6, 3, 2, 8, 5, 7, 1)
()

↓
↓

(4, 6, 3, 2, 7, 1)
(8, 5)

↓
↓

(3, 2, 7, 1)
(4, 6, 8, 5)

↓
↓

(3, 1)
(2, 7, 4, 6, 8, 5)

↓
↓

()
(3, 1, 2, 7, 4, 6, 8, 5)



Sample input:
4
3 2 4 1


Sample output:
3 1 2 4

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n = int(input())
p = [int(x) for x in input().split()]


class SegmentTree:  # 0-indexed
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        return self.tree[self.N-1:]

    def update(self, k, x):
        k += self.N-1
        self.tree[k] = x
        while k+1:
            k = (k-1)//2
            self.tree[k] = self.opr(self.tree[k*2+1], self.tree[k*2+2])

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 1:
            if p & 1 == 0:
                res = self.opr(res, self.tree[p])
            if q & 1 == 1:
                res = self.opr(res, self.tree[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.opr(res, self.tree[p])
        else:
            res = self.opr(self.opr(res, self.tree[p]), self.tree[q])
        return res


ind = [0]*(n+1)
Odd = SegmentTree([10**30]*n)
Even = SegmentTree([10**30]*n)

for i in range(n):
    ind[p[i]] = i
    if i % 2 == 0:
        Even.update(i, p[i])
    else:
        Odd.update(i, p[i])

cand = []
heappush(cand, (Even.query(0, n), 0, n, True))

q = []
while len(q) < n:
    first, l, r, is_even = heappop(cand)
    if is_even:
        second = Odd.query(ind[first]+1, r)
        q.extend([first, second])
        if l < ind[first]:
            heappush(cand, (Even.query(l, ind[first]), l, ind[first], True))
        if ind[first] + 1 < ind[second]:
            heappush(
                cand, (Odd.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], False))
        if ind[second]+1 < r:
            heappush(
                cand, (Even.query(ind[second], r), ind[second]+1, r, True))
    else:
        second = Even.query(ind[first]+1, r)
        q.extend([first, second])
        if l < ind[first]:
            heappush(cand, (Odd.query(l, ind[first]), l, ind[first], False))
        if ind[first] + 1 < ind[second]:
            heappush(
                cand, (Even.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], True))
        if ind[second]+1 < r:
            heappush(
                cand, (Odd.query(ind[second], r), ind[second]+1, r, False))

print(*q)

Submission status: Accepted

Solution code:
import heapq
import sys
input=sys.stdin.readline

class SegmentTreeMin():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=min(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=min(ret,self.tree[r])
      r=(r-1)//2
      ret=min(ret,self.tree[l])
      l=(l+1)//2
    return ret

n=int(input())
arr=list(map(int,input().split()))
odds=SegmentTreeMin(n//2,10**18)
evens=SegmentTreeMin(n//2,10**18)
dic={}
for i in range(n):
  dic[arr[i]]=i
  if i%2==0:
    odds.update(i//2,arr[i])
  else:
    evens.update(i//2,arr[i])
q=[]
heapq.heappush(q,(odds.query(0,(n-1)//2),0,n-1))
ans=[]
while len(q)!=0:
  _,l,r=heapq.heappop(q)
  if l%2==0:
    a=odds.query(l//2,r//2)
    odds.update(dic[a]//2,10**18)
    b=evens.query(dic[a]//2,r//2)
    evens.update(dic[b]//2,10**18)
    ans.append(a)
    ans.append(b)
    tl=dic[a]
    tr=dic[b]
    if tl!=l:
      heapq.heappush(q,(odds.query(l//2,(tl-1)//2),l,tl-1))
    if tl+1<tr-1:
      heapq.heappush(q,(evens.query((tl+1)//2,(tr-1)//2),tl+1,tr-1))
    if tr!=r:
      heapq.heappush(q,(odds.query((tr+1)//2,r//2),tr+1,r))
  else:
    a=evens.query(l//2,r//2)
    evens.update(dic[a]//2,10**18)
    b=odds.query((dic[a]+1)//2,r//2)
    odds.update(dic[b]//2,10**18)
    ans.append(a)
    ans.append(b)
    tl=dic[a]
    tr=dic[b]
    if tl!=l:
      heapq.heappush(q,(evens.query(l//2,(tl-1)//2),l,tl-1))
    if tl+1<tr-1:
      heapq.heappush(q,(odds.query((tl+1)//2,(tr-1)//2),tl+1,tr-1))
    if tr!=r:
      heapq.heappush(q,(evens.query((tr+1)//2,r//2),tr+1,r))
print(*ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    p = list(map(lambda x: int(x)-1, input().split()))

    pos = [j for i, j in sorted([(j, i) for i, j in enumerate(p)])]
    basesize = n >> 1
    num = 1
    while num < basesize:
        num *= 2
    num -= 1

    tree_even = [100001]*(num*2+1)
    tree_odd = [100001]*(num*2+1)

    for i in range(num, num+basesize):
        tree_even[i] = p[(i-num)*2]
    for i in range(num-1, -1, -1):
        tree_even[i] = min(tree_even[2*i+1:2*i+3])
    for i in range(num, num+basesize):
        tree_odd[i] = p[(i-num)*2+1]
    for i in range(num-1, -1, -1):
        tree_odd[i] = min(tree_odd[2*i+1:2*i+3])

    g = dict()
    d = dict()
    q = [n-1]
    qap, qp = q.append, q.pop
    while q:
        t = qp()
        m, M = t//n, t % n
        if m+1 == M:
            d[t] = p[m]*n+p[M]
            continue
        g[t] = []
        gap = g[t].append
        if m % 2 == 0:
            i1, j1 = m >> 1, (M >> 1)+1
            even = 200000
            l, r = i1+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    even = min(even, tree_even[r])
                if l % 2 == 0:
                    even = min(even, tree_even[l])
                    l += 1
                l >>= 1
                r >>= 1
            even_idx = pos[even]
            odd = 200000
            l, r = (even_idx >> 1)+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    odd = min(odd, tree_odd[r])
                if l % 2 == 0:
                    odd = min(odd, tree_odd[l])
                    l += 1
                l >>= 1
                r >>= 1
            odd_idx = pos[odd]
            d[t] = even*n+odd
            if m != even_idx:
                s = m*n+even_idx-1
                qap(s)
                gap(s)
            if M != odd_idx:
                s = (odd_idx+1)*n+M
                qap(s)
                gap(s)
            if even_idx+1 != odd_idx:
                s = (even_idx+1)*n+odd_idx-1
                qap(s)
                gap(s)
        else:
            i1, j1 = m >> 1, M >> 1
            odd = 200000
            l, r = i1+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    odd = min(odd, tree_odd[r])
                if l % 2 == 0:
                    odd = min(odd, tree_odd[l])
                    l += 1
                l >>= 1
                r >>= 1
            odd_idx = pos[odd]
            even = 200000
            l, r = (odd_idx >> 1)+1+num, j1+1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    even = min(even, tree_even[r])
                if l % 2 == 0:
                    even = min(even, tree_even[l])
                    l += 1
                l >>= 1
                r >>= 1
            even_idx = pos[even]
            d[t] = odd*n+even
            if m != odd_idx:
                s = m*n+odd_idx-1
                qap(s)
                gap(s)
            if M != even_idx:
                s = (even_idx+1)*n+M
                qap(s)
                gap(s)
            if odd_idx+1 != even_idx:
                s = (odd_idx+1)*n+even_idx-1
                qap(s)
                gap(s)

    g2 = dict()

    for i, t in g.items():
        k = d[i]
        g2[k] = []
        ga = g2[k].append
        for j in t:
            ga(d[j])

    import heapq
    h = [d[n-1]]
    heapq.heapify(h)
    ans = []
    hpop = heapq.heappop
    hpush = heapq.heappush

    while h:
        t = hpop(h)
        ans += [t//n+1, t % n+1]
        if t in g2:
            for s in g2[t]:
                hpush(h, s)

    print(*ans)


main()

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y):
    if y[0]>x[0]:
        return x
    else:
        return y
#################

#####ide_ele#####
ide_ele =(float("inf"),-1)
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import heapq

N=int(input())
p=list(map(int,input().split()))
n=N//2
op=[(p[2*i+1],2*i+1) for i in range(n)]
ep=[(p[2*i],2*i) for i in range(n)]

oseg=SegTree(op,segfunc,ide_ele)
eseg=SegTree(ep,segfunc,ide_ele)

def first(l,r):
    if l>=r:
        return (-1,-1,-1,-1)
    if l%2==0:
        val,index=eseg.query(l//2,r//2)
        val2,index2=oseg.query(index//2,r//2)
        return (val,val2,index,index2)
    else:
        val,index=oseg.query(l//2,r//2)
        val2,index2=eseg.query(index//2+1,r//2+1)
        return (val,val2,index,index2)

val,val2,index,index2=first(0,N)
que=[((val,val2),0,N)]
heapq.heapify(que)
ans=[]
while que:
    tuple,l,r=heapq.heappop(que)
    ans.append(tuple[0])
    ans.append(tuple[1])
    val,val2,index,index2=first(l,r)
    val,val2,l1,r1=first(l,index)
    if val!=-1:
        heapq.heappush(que,((val,val2),l,index))
    val,val2,l2,r2=first(index+1,index2)
    if val!=-1:
        heapq.heappush(que,((val,val2),index+1,index2))
    val,val2,l3,r3=first(index2+1,r)
    if val!=-1:
        heapq.heappush(que,((val,val2),index2+1,r))

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.buffer.readline

    # min
    def STfunc(a, b):
        if a < b:
            return a
        else:
            return b

    # クエリは0-indexedで[l, r)
    class SparseTable():
        def __init__(self, A):
            # A: 処理したい数列
            self.N = len(A)
            self.K = self.N.bit_length() - 1
            self.table = [[0] * (self.K + 1) for _ in range(self.N)]
            for i, a in enumerate(A):
                self.table[i][0] = A[i]
            for k in range(1, self.K + 1):
                for i in range(self.N):
                    j = i + (1 << (k - 1))
                    if j <= self.N - 1:
                        self.table[i][k] = STfunc(self.table[i][k - 1], self.table[j][k - 1])
                    else:
                        self.table[i][k] = self.table[i][k - 1]

        def query(self, l, r):
            # [l, r)の最小値を求める
            k = (r - l).bit_length() - 1
            return STfunc(self.table[l][k], self.table[r - (1 << k)][k])

    N = int(input())
    n = N//2
    A = list(map(int, input().split()))

    A_even = A[0:N:2]
    A_odd = A[1:N:2]
    ST_even = SparseTable(A_even)
    ST_odd = SparseTable(A_odd)
    val2idx = [0] * (N+1)
    for i in range(N):
        val2idx[A[i]] = i

    ans = []
    ans_append = ans.append
    pq = [(ST_even.query(0, n), 0, N)]
    for t in range(n):
        v1, left, right = heappop(pq)
        ans_append(v1)
        i = val2idx[v1]
        if i & 1:
            v2 = ST_even.query((i+1)//2, right//2 + 1)
            ans_append(v2)
            j = val2idx[v2]
            if left != i:
                heappush(pq, (ST_odd.query(left//2, i//2), left, i))
            if j-i > 1:
                heappush(pq, (ST_even.query((i+1)//2, j//2), i+1, j))
            if j+1 != right:
                heappush(pq, (ST_odd.query((j+1)//2, right//2), j+1, right))
        else:
            v2 = ST_odd.query(i//2, right//2)
            ans_append(v2)
            j = val2idx[v2]
            if left != i:
                heappush(pq, (ST_even.query(left//2, i//2), left, i))
            if j-i > 1:
                heappush(pq, (ST_odd.query((i+1)//2, j//2), i+1, j))
            if j+1 != right:
                heappush(pq, (ST_even.query((j+1)//2, right//2), j+1, right))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import heapq
import sys
input = sys.stdin.readline


class SparseTable():
    """区間取得クエリをO(1)で答えるデータ構造をO(NlogN)で構築する
    query(l, r): 区間[l, r)に対するクエリに答える
    """
    def __init__(self, array, n):
        n = len(array)
        self.row_size = n.bit_length()

        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1

        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
                self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                            self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        """クエリの内容"""
        return min(num1, num2)

    def query(self, l, r):
        """区間[l, r)に対するクエリに答える"""
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])


n = int(input())
p = list(map(int, input().split()))

q = [[0] * (n // 2) for i in range(2)]

for i in range(n):
    q[i%2][i//2] = p[i]

ind = {}
for i in range(n):
    ind[p[i]] = i

sp0 = SparseTable(q[0], n // 2)
sp1 = SparseTable(q[1], n // 2)

con = {}
ans = {}
div = 10**6
def solve(l, r):
    q = deque([l * div + r])
    while q:
        pos = q.pop()
        l, r = pos // div, pos % div 
        # min1 = min(q[l%2][l//2:r//2])
        if l % 2 == 0:
            min1 = sp0.query(l//2, r//2)
        else:
            min1 = sp1.query(l//2, r//2)
        use_pos1 = ind[min1]
        
        # min2 = min(q[(l+1)%2][(use_pos1+1)//2:(r+1)//2])
        if (l + 1) % 2 == 0:
            min2 = sp0.query((use_pos1 + 1) // 2, (r + 1) // 2)
        else:
            min2 = sp1.query((use_pos1 + 1) // 2, (r + 1) // 2)
        use_pos2 =  ind[min2]
        
        ans[pos] = min1 * div + min2
        con[pos] = []
        if l != use_pos1:
            con[pos].append(l * div + use_pos1)
            q.append(l * div + use_pos1)
        if use_pos1 + 1 != use_pos2:
            con[pos].append((use_pos1 + 1) * div + use_pos2)
            q.append((use_pos1 + 1) * div + use_pos2)
        if use_pos2 + 1 != r:
            con[pos].append((use_pos2 + 1) * div + r)
            q.append((use_pos2 + 1) * div + r)

    return


solve(0, n)
res = []
q = [(ans[n], n)]
while q:
    num, i = heapq.heappop(q)
    min1, min2 = num // div, num % div
    res.append(min1)
    res.append(min2)
    for new_num in con[i]:
        heapq.heappush(q, (ans[new_num], new_num))
print(*res)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 1 << 32
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class Segtree:
    def __init__(self, A, ide_ele, segfunc, initialize=True):
        self.n = len(A)
        self.size = 2 ** (self.n - 1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        if initialize:
            self.data = [ide_ele] * self.size + A + [ide_ele] * (self.size - self.n)
            for i in range(self.size - 1, 0, -1):
                self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])
        else:
            self.data = [ide_ele] * (2 * self.size)

    def update(self, k, x):
        k += self.size
        self.data[k] = x
        while k > 0:
            k = k >> 1
            self.data[k] = self.segfunc(self.data[2 * k], self.data[2 * k + 1])

    def query(self, l, r):
        L, R = l + self.size, r + self.size
        s = self.ide_ele
        while L < R:
            if R & 1:
                R -= 1
                s = self.segfunc(s, self.data[R])
            if L & 1:
                s = self.segfunc(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

n = I()
P = LI()
D = {P[i]: i for i in range(n)}
p_even = [P[i] if not i & 1 else INF for i in range(n)]
p_odd = [P[i] if i & 1 else INF for i in range(n)]
st_even = Segtree(p_even, INF, min)
st_odd = Segtree(p_odd, INF, min)
hq = [(st_even.query(0, n), 0, n)]
ans = []
for _ in range(n // 2):
    v1, l, r = heappop(hq)
    p1 = D[v1]
    if not l & 1:
        st1, st2 = st_odd, st_even
    else:
        st1, st2 = st_even, st_odd
    v2 = st1.query(p1, r)
    p2 = D[v2]
    st2.update(p1, INF)
    st1.update(p2, INF)
    if l != p1:
        heappush(hq, (st2.query(l, p1), l, p1))
    if p1 + 1 != p2:
        heappush(hq, (st1.query(p1 + 1, p2), p1 + 1, p2))
    if p2 + 1 != r:
        heappush(hq, (st2.query(p2 + 1, r), p2 + 1, r))
    ans += [v1, v2]


print(*ans)

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

# lから1つおきにみたときの最小値を求める特別製
class SparseTable:
    def __init__(self, aa):
        inf = 10 ** 16
        w = len(aa)
        h = w.bit_length()
        table = [aa] * 2 + [[inf] * w for _ in range(h - 2)]
        tablei1 = table[0]
        for i in range(2, h):
            tablei = table[i]
            shift = 1 << (i - 1)
            for j in range(w):
                rj = j + shift
                if rj >= w: break
                tablei[j] = min(tablei1[j], tablei1[rj])
            tablei1 = tablei
        self.table = table

    # [l,r)の最小値
    def min(self, l, r):
        if (r - l) % 2: r += 1
        i = (r - l).bit_length() - 1
        tablei = self.table[i]
        Lmin = tablei[l]
        Rmin = tablei[r - (1 << i)]
        if Lmin < Rmin: Rmin = Lmin
        return Rmin

def main():
    n = int(input())
    pp = LI()
    st = SparseTable(pp)
    ptoi = [0] + [i for i, p in sorted(enumerate(pp), key=lambda x: x[1])]
    # 区間偶数番目の最小値と[l,r)をヒープに
    hp = []
    heappush(hp, [st.min(0, n), 0, n])
    ans = []
    for _ in range(n // 2):
        x, l, r = heappop(hp)
        if l + 2 == r:
            ans += [pp[l], pp[l + 1]]
            continue
        xi = ptoi[x]
        y = st.min(xi + 1, r)
        yi = ptoi[y]
        if xi > l:
            heappush(hp, [st.min(l, xi), l, xi])
        if xi + 1 < yi:
            heappush(hp, [st.min(xi + 1, yi), xi + 1, yi])
        if yi < r - 1:
            heappush(hp, [st.min(yi + 1, r), yi + 1, r])
        ans += [x, y]
    print(*ans)

main()

Submission status: Accepted

Solution code:
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')