結果

問題 No.2809 Sort Query
コンテスト
ユーザー もろこし
提出日時 2025-12-12 18:00:20
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 9,512 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 540 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 271,064 KB
最終ジャッジ日時 2025-12-12 18:01:04
合計ジャッジ時間 39,192 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 RE * 10 TLE * 6 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
sys.setrecursionlimit(10**7)
def ii(): return int(input())
def mi(d=0): return map(lambda x:int(x)-d,input().split())
################################################
class AVLTree:
  def __init__(self,debugmode=False):
    self.nodes:dict[AVLTree.Node] = {}
    self.keys = set([])
    self.debugmode = debugmode

  def add(self,key:int,count=1):
    """木に新しいノードを追加する。すでにあるならcount+1"""
    if len(self.keys):
      if not key in self.keys:
        self.root,new_node = self.root.add(key,count)
        self.nodes[key] = new_node
        self.keys.add(key)
      else:
        # self.debugLog(f"node{key} += {count}")
        node:AVLTree.Node = self.nodes[key]
        node.count += count
        while node.parent:
          node = node.parent
          node.childCount += count
      if self.debugmode:
        self.root.check()
    else:
      self.root = AVLTree.Node(key,count,AVLTree.NONE)
      self.keys.add(key)
      self.nodes[key] = self.root
  
  def remove(self,key,count=1):
    """keyをcount個だけ削除する。0個になったらバランスを根まで確認。"""
    if key in self.keys:
      target:AVLTree.Node = self.nodes[key]
      if target.count > count:
        target.count -= count
        while target.parent:
          target = target.parent
          target.childCount -= count
        # self.debugLog(f"decline {key}")
      else:
        # self.debugLog(f"delete {key}")
        ch:AVLTree.Node;rep:AVLTree.Node = target,target
        #rep:targetと入れ替えるノード
        #ch:バランスチェックの開始地点
        if target.left:
          if target.right:
            rep = target.right.getBiggerMin(-10**9+1)
            # self.debugLog(f"swap {target.key} to {rep.key}")
            ch = rep
            if target.right != rep:
              self.changeParent(rep,rep.right)
              rep.right = target.right
              target.right.parent = rep
              ch = rep.parent
            rep.left = target.left
            target.left.parent = rep
            # self.root.check()
          else:
            rep = target.left
            ch = target.parent
        else:
          ch = target.parent
          if target.right:
            rep = target.right
          else:
            rep = AVLTree.NONE
        self.changeParent(target,rep)
        self.root = self.checkBalances(ch)
        self.keys.remove(key)
        del self.nodes[key]
        if self.debugmode:
          self.root.check()
  
  def checkBalances(self,node:'AVLTree.Node'):
    """指定したノードから根までのバランスを確認する。"""
    while node:
      node.calcHeight()
      np = node.parent
      if np:
        if np < node:
          np.right = node.checkBalance()
        else:
          np.left = node.checkBalance()
      else:
        return node.checkBalance()
      node = np
  
  def changeParent(self,f:'AVLTree.Node',t:'AVLTree.Node'):
    """fの親の子要素をtに入れ替える。"""
    p = f.parent
    if not p:
      # self.debugLog("root delete!")
      self.root = t
      t.parent = AVLTree.NONE
      return
    else:
      if p < f:
        p.right = t
      else:
        p.left = t
    if t:
      t.parent = p

  def debugLog(self,string):
    if self.debugmode:
      print(string)

  def getNexts(self,key):
    """ノードをkey順に並べたとき、指定したノードの左右のノードを返す"""
    if key in self.keys:
      s = self.root.getSmallerMax(key)
      b = self.root.getBiggerMin(key)
    return s,b
  def __getitem__(self,index):
    i = 0
    node = self.root
    while True:
      leftcount = node.left.childCount + i + node.left.count
      if leftcount <= index < leftcount + node.count:
        return node.key
      elif leftcount + node.count <= index:
        i += leftcount + node.count - i
        node = node.right
      else:
        node = node.left
  def __len__(self):
    return self.root.childCount + self.root.count
  
  def solve(self):
    n,q = mi()
    a = list(mi())
    for aa in a:
      self.add(aa)
    change_keys = set([])
    for _ in range(q):
      query = input()
      if query[0] == "1":
        _,k,x = map(int,query.split())
        change_keys.add(k-1)
        a[k-1] = (self[k-1],x)
      elif query[0] == "2":
        for k in change_keys:
          self.remove(a[k][0])
        for k in change_keys:
          self.add(a[k][1])
        change_keys.clear()
      else:
        _,k = map(int,query.split())
        if k-1 in change_keys:
          print(a[k-1])
        else:
          print(self[k-1])

  class Node:
    """ノードを表す。"""
    def __init__(self,key,count,parent):
      self.key = key
      self.count = count
      self.left:AVLTree.Node = AVLTree.NONE
      self.right:AVLTree.Node = AVLTree.NONE
      self.height:int = 1
      self.parent = parent
      self.childCount = 0

    def add(self,key,count=1,quick=False)->tuple['AVLTree.Node','AVLTree.Node']:
      """
      新しいノードの追加場所を自分の子供から探す。
      追加したならバランスを調整し、回転後に自分の位置に来るノードと追加された新しいノードを返す。
      """
      new_node:AVLTree.Node|AVLTree.Null = AVLTree.NONE
      if key < self:
        if self.left:
          self.left,new_node = self.left.add(key,count)
        else:
          self.left = AVLTree.Node(key,count,self)
          new_node = self.left
      if key > self:
        if self.right:
          self.right,new_node = self.right.add(key,count)
        else:
          self.right = AVLTree.Node(key,count,self)
          new_node = self.right
      if quick:
        return self,new_node
      self.calcHeight()
      return self.checkBalance(),new_node


    def getBalance(self)->int:
      """ノードの傾きを取得"""
      return self.left.height - self.right.height
    
    def checkBalance(self)->'AVLTree.Node':
      """バランスを計算し、傾いているなら回転させる。回転した後の親ノードを返す。"""
      balance = self.getBalance()
      ret = self
      if balance < -1:
        if self.left and self.left.getBalance() <= -1:
          self.left = self.left.swapRight()
        ret = self.swapLeft()
      elif balance > 1:
        if self.right and self.right.getBalance() >= 1:
          self.right = self.right.swapLeft()
        ret = self.swapRight()
      return ret

    def swapRight(self)->'AVLTree.Node':
      """左側をひっぱって自分の位置に移動"""
      left = self.left
      self.parent,left.parent = left,self.parent
      self.left,left.right = left.right,self
      self.left.parent = self
      self.calcHeight()
      left.calcHeight()
      return left


    def swapLeft(self)->'AVLTree.Node':
      """右側をひっぱって自分の位置に移動"""
      right = self.right
      self.parent,right.parent = right,self.parent
      self.right,right.left = right.left,self
      self.right.parent = self
      self.calcHeight()
      right.calcHeight()
      return right
    

    def calcHeight(self):
      """高さと子要素の数を更新"""
      self.height = max(self.left.height,self.right.height)+1
      self.childCount = self.left.childCount + self.right.childCount + self.left.count + self.right.count

    def getSmallerMax(self,x=10**9+1):
      """xより小さい最大値を取得"""
      if self > x:
        if self.left:
          return self.left.getSmallerMax(x)
        else:
          return AVLTree.NONE
      elif self < x:
        if self.right:
          r = self.right.getSmallerMax(x)
          return r if r else self
        else:
          return self
    def getBiggerMin(self,x=-10**9+1):
      """xより大きい最小値を取得"""
      if self < x:
        if self.right:
          return self.right.getBiggerMin(x)
        else:
          return AVLTree.NONE
      elif self > x:
        if self.left:
          l = self.left.getBiggerMin(x)
          return l if l else self
        else:
          return self

    def check(self,flag=False):
      q = [self]
      i = 0
      while q:
        nq = []
        if flag:
          print(*map(lambda x:(str(x),x.childCount,str(x.parent),str(x.left),str(x.right)),q))
        else:
          print(*map(str,q))
        f = False
        for qq in q:
          nq.append(qq.left if qq.left else AVLTree.NONE)
          f |= bool(qq.left)
          nq.append(qq.right if qq.right else AVLTree.NONE)
          f |= bool(qq.right)
        q = nq
        i += 1
        if not f or i > 5:
          break


    def __str__(self):
      return str(self.key)
    def __lt__(self,other):
      if type(other) == AVLTree.Node:
        return self.key < other.key
      elif type(other) == int:
        return self.key < other
      else:
        print(other,"?")
        raise TypeError
    def __gt__(self,other):
      if type(other) == AVLTree.Node:
        return self.key > other.key
      elif type(other) == int:
        return self.key > other
      else:
        print(other,"?")
        raise TypeError


  class Null(Node):
    """空のノード"""
    def __init__(self):
      self.key = -1
      self.count = 0
      self.left = None
      self.right = None
      self.parent = None
      self.height = 0
      self.childCount = 0
    def __bool__(self):
      return False
    def __str__(self):
      return "x"
  NONE = Null()

tree = AVLTree()
tree.solve()
0