백준 13159 - 배열 [Python]

https://www.acmicpc.net/problem/13159

13159번: 배열

[알고리즘 분류]

스플레이 트리

 

 

2번정도 구현해보기만 했던 스플레이 트리.. 막상 해보니 그렇게까지 어렵지는 않았다. 아마도..?

 

https://cubelover.tistory.com/10

위 글을 참고하였다. 감사합니다..

 

import sys
 
input = sys.stdin.readline
 
 
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
 
 
############ Main! #############
 
INF = 10 ** 9 + 7
 
class Node:
    def __init__(self, l=None, r=None, p=None, v=0, sz=1):
        self.l = l
        self.r = r
        self.p = p
        self.sz = sz
        self.sum = self.mn = self.mx = self.v = v
        self.dummy = False
        self.flip = False
 
class SplayTree:
    def __init__(self, n):
        self.ptr = [Node() for _ in range(n + 2)]
        self.ptr[0] = x = self.root = Node(v=-INF)
        for i in range(1, n + 1):
            self.ptr[i] = x.r = Node(v=i, p=x)
            x = x.r
        self.ptr[n + 1] = x.r = Node(v=INF, p=x)
        self.root.dummy = x.r.dummy = True
        for i in range(n, 0, -1):
            self.update(self.ptr[i])
        self.splay(self.ptr[n // 2])
 
    def update(self, x):
        x.sz = 1
        x.sum = x.mn = x.mx = x.v
        if x.l is not None:
            x.sz += x.l.sz
            x.sum += x.l.sum
            x.mn = min(x.mn, x.l.mn)
            x.mx = max(x.mx, x.l.mx)
        if x.r is not None:
            x.sz += x.r.sz
            x.sum += x.r.sum
            x.mn = min(x.mn, x.r.mn)
            x.mx = max(x.mx, x.r.mx)
 
    def push(self, x):
        if not x.flip:
            return
        x.l, x.r = x.r, x.l
        if x.l is not None:
            x.l.flip ^= 1
        if x.r is not None:
            x.r.flip ^= 1
        x.flip = 0
 
    def gather(self, s, e):
        self.kth(s - 1)
        x = self.root
        self.root = x.r
        self.root.p = None
        self.kth(e - s + 1)
        x.r = self.root
        self.root.p = x
        self.root = x
        return self.root.r.l
 
    def rotate(self, x):
        p = x.p
        y: Node
        self.push(p)
        self.push(x)
        if x == p.l:
            p.l = y = x.r
            x.r = p
        else:
            p.r = y = x.l
            x.l = p
        x.p = p.p
        p.p = x
        if y is not None:
            y.p = p
        if x.p is not None:
            if x.p.l == p:
                x.p.l = x
            else:
                x.p.r = x
        else:
            self.root = x
        self.update(p)
        self.update(x)
 
    def splay(self, x, g=None):
        while x.p != g:
            p = x.p
            if p.p == g:
                self.rotate(x)
                break
            pp = p.p
            if (p.l == x) == (pp.l == p):
                self.rotate(p)
                self.rotate(x)
            else:
                self.rotate(x)
                self.rotate(x)
        if g is not None:
            self.root = x
 
    def flip(self, s, e):
        x = self.gather(s, e)
        x.flip ^= 1
 
    def shift(self, s, e, k):
        x = self.gather(s, e)
        print(x.mn, x.mx, x.sum)
        if k >= 0:
            k %= e - s + 1
            if k == 0:
                return
            self.flip(s, e)
            self.flip(s, s + k - 1)
            self.flip(s + k, e)
        else:
            k = -k
            k %= e - s + 1
            if k == 0:
                return
            self.flip(s, e)
            self.flip(s, e - k)
            self.flip(e - k + 1, e)
 
    def getidx(self, k):
        self.splay(self.ptr[k])
        print(self.root.l.sz)
 
    def kth(self, k):
        x = self.root
        self.push(x)
        while True:
            while x.l is not None and x.l.sz > k:
                x = x.l
                self.push(x)
            if x.l:
                k -= x.l.sz
            if k == 0:
                break
            k -= 1
            x = x.r
            self.push(x)
        self.splay(x)
 
    def prt(self, x):
        s = []
        ret = []
        while True:
            if x is not None:
                self.push(x)
                s.append(x)
                x = x.l
            elif s:
                x = s.pop()
                if not x.dummy:
                    print(x.v, end=" ")
                x = x.r
            else:
                break
        return ret
 
N, q = mip()
tree = SplayTree(N)
 
for i in range(q):
    Q = lmip()
    if Q[0] == 1:
        tree.flip(Q[1], Q[2])
        x = tree.gather(Q[1], Q[2])
        print(x.mn, x.mx, x.sum)
    elif Q[0] == 2:
        tree.shift(Q[1], Q[2], Q[3])
    elif Q[0] == 3:
        tree.kth(Q[1])
        print(tree.root.v)
    else:
        tree.getidx(Q[1])
tree.prt(tree.root)
 
######## Praise greedev ########

솔브닥 티어만 잘 오르는 자료구조...