結果

問題 No.3167 [Cherry 7th Tune C] Cut in Queue
ユーザー norioc
提出日時 2025-06-02 09:06:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,218 ms / 2,500 ms
コード長 5,128 bytes
コンパイル時間 545 ms
コンパイル使用メモリ 82,156 KB
実行使用メモリ 355,908 KB
最終ジャッジ日時 2025-06-02 09:07:43
合計ジャッジ時間 59,714 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SplittableLinkedList:
    class Node:
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None

    def __init__(self):
        self.head = None
        self.tail = None

    def __iter__(self):
        node = self.head
        while node:
            yield node.val
            node = node.right

    @staticmethod
    def _connect(a: Node, b: Node):
        """a と b を接合する"""
        a.right = b
        b.left = a

    @staticmethod
    def link(a: 'SplittableLinkedList', b: 'SplittableLinkedList') -> 'SplittableLinkedList':
        if a.head is None: return b
        if b.head is None: return a

        a.tail.right = b.head
        b.head.left = a.tail

        res = SplittableLinkedList()
        res.head = a.head
        res.tail = b.tail
        return res

    def append(self, val) -> Node:
        node = SplittableLinkedList.Node(val)
        if self.head is None:
            self.head = self.tail = node
        else:
            SplittableLinkedList._connect(self.tail, node)
            self.tail = node

        return node

    def appendleft(self, val) -> Node:
        node = SplittableLinkedList.Node(val)
        if self.head is None:
            self.head = self.tail = node
        else:
            SplittableLinkedList._connect(node, self.head)
            self.head = node

        return node

    def remove(self, node: Node):
        if node is self.head:
            self.head = self.head.right
            if self.head:
                self.head.left = None
        elif node is self.tail:
            self.tail = self.tail.left
            if self.tail:
                self.tail.right = None
        else:
            left = node.left
            right = node.right
            left.right = right
            right.left = left

    def split_before(self, node: Node) -> tuple['SplittableLinkedList', 'SplittableLinkedList']:
        assert node is not None
        a = SplittableLinkedList()
        if node.left:
            a.head = self.head
        a.tail = node.left

        b = SplittableLinkedList()
        b.head = node
        b.tail = self.tail

        if a.tail:
            a.tail.right = None
        b.head.left = None
        return a, b

    def split_after(self, node: Node) -> tuple['SplittableLinkedList', 'SplittableLinkedList']:
        assert node is not None
        a = SplittableLinkedList()
        a.head = self.head
        a.tail = node

        b = SplittableLinkedList()
        b.head = node.right
        if b.head:
            b.tail = self.tail

        a.tail.right = None
        if b.head:
            b.head.left = None
        return a, b


class FenwickTree:
    def __init__(self, n: int):
        self.data = [0] * (n+10)
        self.n = (n+10)

    def add(self, p: int, x: int):
        assert 0 <= p < self.n
        p += 1
        while p < len(self.data):
            self.data[p] += x
            p += p & -p

    def sum(self, p: int) -> int:
        """区間 [0, p] の和"""
        assert 0 <= p < self.n
        p += 1
        s = 0
        while p > 0:
            s += self.data[p]
            p -= p & -p
        return s

    def rangesum(self, l: int, r: int) -> int:
        """区間 [l, r] の和"""
        assert 0 <= l <= r < self.n
        s = self.sum(r)
        if l > 0:
            s -= self.sum(l-1)
        return s


from collections import deque

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

ll = SplittableLinkedList()
v2node = {}
for a in A:
    node = ll.append(a)
    v2node[a] = node

Q = int(input())
queries = []
bs = deque(range(N+1, N+Q+1))
for _ in range(Q):
    qs = list(map(int, input().split()))
    # print(f'{qs=}')
    queries.append(qs)
    if qs[0] == 1:
        a = qs[1]
        b = bs.popleft()
        if a == 0:
            v2node[b] = ll.append(b)
        else:
            node = v2node[a]
            x, y = ll.split_before(node)
            v2node[b] = x.append(b)
            ll = SplittableLinkedList.link(x, y)

v2i = {}
values = []
for i, v in enumerate(ll):
    v2i[v] = i
    values.append(v)


ft = FenwickTree(N+Q+10)
ll = SplittableLinkedList()
v2node = {}
for a in A:
    v2node[a] = ll.append(a)
    ft.add(v2i[a], 1)


def kth(k):
    lo = 0
    hi = N+Q
    res = hi
    while lo <= hi:
        m = (lo + hi) // 2
        cnt = ft.sum(m)
        if cnt >= k:
            res = min(res, m)
            hi = m - 1
        else:
            lo = m + 1

    return res


bs = deque(range(N+1, N+Q+1))
for i in range(len(queries)):
    qs = queries[i]
    if qs[0] == 1:
        a = qs[1]
        b = bs.popleft()
        ft.add(v2i[b], 1)
        if a == 0:
            v2node[b] = ll.append(b)
        else:
            node = v2node[a]
            x, y = ll.split_before(node)
            v2node[b] = x.append(b)
            ll = SplittableLinkedList.link(x, y)
    elif qs[0] == 2:
        node = ll.head
        ft.add(v2i[node.val], -1)
        ll.remove(node)
    else:
        k = qs[1]
        ind = kth(k)
        # print(f'{ind=} {values[ind]}')
        print(values[ind])
0