#1139991 (PyPy3) No.2809 Sort Query

• 問題: No.2809 Sort Query
• ユーザー: もろこし
• 提出日時: 2025-12-11 19:32:38
• 言語: PyPy3 (7.3.15)
• 結果: TLE
• 実行時間: -
• コード長: 8,830 bytes
• コンパイル時間: 1,050 ms
• コンパイル使用メモリ: 82,308 KB
• 実行使用メモリ: 64,400 KB
• 最終ジャッジ日時: 2025-12-11 19:32:50
• 合計ジャッジ時間: 12,072 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
other	AC * 1 TLE * 1 -- * 69

ソースコード

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 = {}
    self.keys = set([])
    self.debugmode = debugmode

    self.changes = []
    self.changeKeys = set([])

  #ノードの追加。
  def add(self,key,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}")
        self.nodes[key].count += count
        node:AVLTree.Node = self.nodes[key]
        while node:
          node.calcHeight()
          node = node.parent
      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):
    if key in self.keys:
      target = self.nodes[key]
      if target.count > 1:
        target.count -= 1
        while target:
          target.calcHeight()
          target = target.parent
        self.debugLog(f"decline {key}")
      else:
        self.debugLog(f"delete {key}")
        ch,rep = target,target
        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):
    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,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)

  #ノードをkey順に並べたとき、指定したノードの左右のノードを返す
  def getNexts(self,key):
    if key in self.keys:
      s = self.root.getSmallerMax(key)
      b = self.root.getBiggerMin(key)
    return s,b
  def __getitem__(self,index):
    if len(self) > index:
      i = 0
      node = self.root
      while True:
        # print(node.key,i)
        leftcount = node.left.childCount + i + node.left.count
        if leftcount <= index < leftcount + node.count:
          return node
        elif leftcount + node.count <= index:
          i += leftcount + node.count - i
          node = node.right
        else:
          node = node.left
    else:
      return AVLTree.NONE
  def __len__(self):
    return self.root.childCount + self.root.count
  
  def sort(self):
    # print(self.changeKeys)
    # print(self.changes)
    add = []
    for k in self.changeKeys:
      node,x = self.changes[k]
      self.debugLog(f"remove{node.key},add{x}")
      self.remove(node.key)
      add.append(x)
    for ad in add:
      self.add(ad)
    self.changeKeys.clear()
  def getValue(self,k):
    if k in self.changeKeys:
      return self.changes[k][1]
    else:
      return self[k]

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

    #子ノードを追加する処理。追加した後、バランスを計算して必要なら回転し、回転後の親ノードと追加されたノードを返す。
    def add(self,key,count=1):
      ret = AVLTree.NONE
      if key < self:
        if self.left:
          self.left,ret = self.left.add(key,count)
        else:
          self.left = AVLTree.Node(key,count,self)
          ret = self.left
      if key > self:
        if self.right:
          self.right,ret = self.right.add(key,count)
        else:
          self.right = AVLTree.Node(key,count,self)
          ret = self.right
      self.calcHeight()
      return self.checkBalance(),ret
  
    def getBalance(self):
      return self.left.height - self.right.height
    # バランスを計算し、傾いているなら回転させる。回転した後の親ノードを返す。
    def checkBalance(self):
      balance = self.getBalance()
      ret = self
      if balance < -1:
        ret = self.swapLeft()
      elif balance > 1:
        ret = self.swapRight()
      return ret
    
    #回転処理。回転後に自分の位置に来るノードを返す。
    def swapRight(self):
      if self.left.getBalance() <= -1:
        self.left = self.left.swapLeft()

      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):
      if self.right.getBalance() >= 1:
        self.right = self.right.swapRight()

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

n,q = mi()
a = list(mi())
tree = AVLTree()
f = False
for aa in a:
  tree.add(aa)
  tree.changes.append(-1)

for _ in range(q):
  query = input()
  if query[0] == "1":
    _,k,x = map(int,query.split())
    # print(f"change {tree[k-1].key} to {x}")
    tree.changes[k-1] = (tree[k-1],x)
    tree.changeKeys.add(k-1)
  elif query[0] == "2":
    f = True
    tree.sort()
  else:
    _,k = map(int,query.split())
    if not f:
      print(a[k-1])
    else:
      print(tree.getValue(k-1).key)