AtCoder Beginner Contest 253 C

https://atcoder.jp/contests/abc253/tasks/abc253_c

C++ならstd::mapを使えば簡単ですが、Pythonだとそうはいきません。平衡二分木が無いんですね。解説を読むとPriorityQueueを使えばよいと書かれています。なるほど。
よく考えると、xはあらかじめ決まっているので、それをソートしてふつうに二分木を作ればよいです。

# coding: utf-8
# Max - Min Query

from itertools import *
from collections import Counter
from Queue import PriorityQueue


#################### library ####################

def read_int():
    return int(raw_input())

def read_list():
    return list(map(int, raw_input().split()))


#################### Node ####################

class Node:
    def __init__(self, v):
        self.left       = v[0]
        self.right      = v[-1]
        self.counter    = 0
        if len(v) == 1:
            self.children   = []
        else:
            mid = len(v) / 2
            self.children   = [Node(v[:mid]), Node(v[mid:])]
    
    def is_leaf(self):
        return not self.children
    
    def add(self, x):
        if self.is_leaf():
            self.counter += 1
        else:
            if x <= self.children[0].right:
                self.counter += self.children[0].add(x)
            else:
                self.counter += self.children[1].add(x)
        return 1
    
    def remove(self, x, c):
        if self.is_leaf():
            if x != self.left:
                return 0
            else:
                c1 = min(c, self.counter)
                self.counter -= c1
                return c1
        else:
            if x <= self.children[0].right:
                c1 = self.children[0].remove(x, c)
            else:
                c1 = self.children[1].remove(x, c)
            self.counter -= c1
            return c1
    
    def max(self):
        if self.is_leaf():
            return self.left
        else:
            if self.children[1].counter > 0:
                return self.children[1].max()
            else:
                return self.children[0].max()
    
    def min(self):
        if self.is_leaf():
            return self.left
        else:
            if self.children[0].counter > 0:
                return self.children[0].min()
            else:
                return self.children[1].min()
    
    def __str__(self):
        if self.is_leaf():
            return '(%d, %d)' % (self.left, self.counter)
        else:
            return str(self.children[0]) + str(self.children[1])
    
    @staticmethod
    def create(queries):
        v = sorted(set(q.x for q in queries if isinstance(q, QueryAdd)))
        return Node(v)


#################### Query ####################

def read_queries():
    Q = read_int()
    for _ in range(Q):
        v = read_list()
        yield create_query(v)
    
def create_query(v):
    if v[0] == 1:
        return QueryAdd(v[1])
    elif v[0] == 2:
        return QueryRemove(v[1], v[2])
    else:
        return QueryPrint()

class QueryAdd:
    def __init__(self, x):
        self.x = x
    
    def query(self, tree):
        tree.add(self.x)

class QueryRemove:
    def __init__(self, x, c):
        self.x = x
        self.c = c
    
    def query(self, tree):
        tree.remove(self.x, self.c)
    
    def tuple(self):
        return (2, self.x, self.c)

class QueryPrint:
    def __init__(self):
        pass
    
    def query(self, tree):
        print tree.max() - tree.min()


#################### process ####################

def F(queries):
    tree = Node.create(queries)
    for query in queries:
        query.query(tree)


#################### main ####################

queries = list(read_queries())
F(queries)