Problem:

Set: Range Search

  For a set $S$ of integers, perform a sequence of the following operations. Note that each value in $S$ must be unique.

  
insert($x$): Insert $x$ to $S$ and report the number of elements in $S$ after the operation.

  
find($x$): Report the number of $x$ in $S$ (0 or 1).

  
delete($x$): Delete $x$ from $S$.

  
dump($L$, $R$): Print elements $x$ in $S$ such that $L \leq x \leq R$.

Input

  The input is given in the following format.

$q$
$query_1$
$query_2$
:
$query_q$

Each query $query_i$ is given by

0 $x$

or

1 $x$

or

2 $x$

or

3 $L$ $R$

where the first digits 0, 1, 2 and 3 represent insert, find, delete and dump operations respectively.

Output

For each insert operation, print the number of elements in $S$.

For each find operation, print the number of specified elements in $S$.

For each dump operation, print the corresponding elements in ascending order. Print an element in a line.

Constraints

  
$1 \leq q \leq 200,000$

  
$0 \leq x \leq 1,000,000,000$

The total number of elements printed by dump operations does not exceed $1,000,000$

Sample Input 1

9
0 1
0 2
0 3
2 2
1 1
1 2
1 3
0 4
3 2 4

Sample Output 1

1
2
3
1
0
1
3
3
4



Sample input:
9
0 1
0 2
0 3
2 2
1 1
1 2
1 3
0 4
3 2 4


Sample output:
1
2
3
1
0
1
3
3
4

Submission status: Accepted

Solution code:

from enum import Enum
import math


class Color(Enum):
    BLACK = 0
    RED = 1

    @staticmethod
    def flip(c):
        return [Color.RED, Color.BLACK][c.value]


class RedBlackBinarySearchTree:
    """Red Black Binary Search Tree with range, min, max.
    """

    class Node:
        __slots__ = ('key', 'left', 'right', 'count', 'color')

        def __init__(self, key):
            self.key = key
            self.left = None
            self.right = None
            self.count = 0
            self.color = Color.RED

        def __str__(self):
            if self.color == Color.RED:
                key = '*{}'.format(self.key)
            else:
                key = '{}'.format(self.key)
            return "{}[{}] ({}, {})".format(key, self.count,
                                            self.left, self.right)

    def __init__(self):
        self.root = None

    def put(self, key):
        def _put(node):
            if node is None:
                node = self.Node(key)
            if node.key > key:
                node.left = _put(node.left)
            elif node.key < key:
                node.right = _put(node.right)

            node = self._restore(node)

            node.count = self._size(node.left) + self._size(node.right) + 1
            return node

        self.root = _put(self.root)
        self.root.color = Color.BLACK

    def _is_red(self, node):
        if node is None:
            return False
        else:
            return node.color == Color.RED

    def _is_black(self, node):
        if node is None:
            return False
        else:
            return node.color == Color.BLACK

    def _is_2node(self, node):
        if node is None:
            return False
        elif self._is_red(node):
            return False
        else:
            return (self._is_black(node) and
                    not self._is_red(node.left) and
                    not self._is_red(node.right))

    def _is_34node(self, node):
        if node is None:
            return False
        elif self._is_red(node):
            return True
        else:
            return (self._is_black(node) and
                    self._is_red(node.left) and
                    not self._is_red(node.right))

    def _rotate_left(self, node):
        x = node.right
        node.right = x.left
        x.left = node
        x.color = node.color
        node.color = Color.RED
        node.count = self._size(node.left) + self._size(node.right) + 1
        return x

    def _rotate_right(self, node):
        x = node.left
        node.left = x.right
        x.right = node
        x.color = node.color
        node.color = Color.RED
        node.count = self._size(node.left) + self._size(node.right) + 1
        return x

    def _flip_colors(self, node):
        node.color = Color.flip(node.color)
        node.left.color = Color.flip(node.left.color)
        node.right.color = Color.flip(node.right.color)
        return node

    def __contains__(self, key):
        def _contains(node):
            if node is None:
                return False
            if node.key > key:
                return _contains(node.left)
            elif node.key < key:
                return _contains(node.right)
            else:
                return True
        return _contains(self.root)

    def delete(self, key):
        def _delete_from(node):
            if node is None:
                return None
            else:
                assert not self._is_2node(node)

                if node.key > key:
                    node = self._convert_left(node)
                    # print('_convert_left', node)
                    node.left = _delete_from(node.left)
                    node = self._restore(node)
                    # print('_restore', node)
                elif node.key < key:
                    node = self._convert_right(node)
                    # print('_convert_right', node)
                    node.right = _delete_from(node.right)
                    node = self._restore(node)
                    # print('_restore', node)
                else:
                    node = _remove(node)

            if node is not None:
                node.count = self._size(node.right) + self._size(node.left) + 1
            return node

        def _remove(node):
            if node.left is None:
                return None
            elif node.right is None:
                if self._is_red(node.left):
                    node.left.color = Color.BLACK
                return node.left
            else:
                node = self._convert_right(node)
                if node.key == key:
                    x = self._find_min(node.right)
                    node.key = x.key
                    node.right = self._delete_min(node.right)
                else:
                    # print(node)
                    node.right = _delete_from(node.right)
                node = self._restore(node)
                # print('min', x.key, 'node', node.key)
                return node

        if self.root is None:
            return
        # print('initial', self.root)
        if not self._is_red(self.root.left):
            self.root.color = Color.RED
        self.root = _delete_from(self.root)
        if self.root is not None:
            self.root.color = Color.BLACK

    def delete_max(self):
        if self.root is None:
            raise ValueError('remove max on empty tree')
        if self.root.left is None:
            self.root = None
            return
        if not self._is_red(self.root.left):
            self.root.color = Color.RED
        self.root = self._delete_max(self.root)
        self.root.color = Color.BLACK

    def _delete_max(self, node):
        if node.right is None:
            if self._is_red(node.left):
                node.left.color = Color.BLACK
            return node.left
        else:
            assert not self._is_2node(node)
            node = self._convert_right(node)
            node.right = self._delete_max(node.right)
            node = self._restore(node)
            return node

    def _convert_right(self, node):
        if self._is_2node(node.right):
            if self._is_2node(node.left):
                self._flip_colors(node)
            elif self._is_red(node.left) and self._is_2node(node.left.right):
                node = self._rotate_right(node)
                self._flip_colors(node.right)
            elif self._is_red(node.left):
                x = node.left.right
                node.left.right = x.left
                node.left, node.right, x.left, x.right = \
                    x.right, node.right.left, node.left, node.right
                x.right.left = node
                x.color = Color.BLACK
                node.color = Color.RED
                if self._is_red(x.left.right):
                    x.left.right.color = Color.BLACK
                node.count = (self._size(node.left) +
                              self._size(node.right) + 1)
                x.left.count = (self._size(x.left.left) +
                                self._size(x.left.right) + 1)
                node = x
            elif self._is_34node(node.left):
                x = node.left
                node.left, node.right, x.right = \
                    x.right, node.right.left, node.right
                x.right.left = node
                x.color = node.color
                if self._is_red(x.left):
                    x.left.color = Color.BLACK
                if self._is_black(x.right.left):
                    x.right.left.color = Color.RED
                node.count = (self._size(node.left) +
                              self._size(node.right) + 1)
                x.left.count = (self._size(x.left.left) +
                                self._size(x.left.right) + 1)
                node = x
        return node

    def delete_min(self):
        if self.root is None:
            raise ValueError('remove min on empty tree')
        if self.root.left is None:
            self.root = None
            return
        if not self._is_red(self.root.left):
            self.root.color = Color.RED
        self.root = self._delete_min(self.root)
        self.root.color = Color.BLACK

    def _delete_min(self, node):
        if node.left is None:
            return None
        else:
            node = self._convert_left(node)
            node.left = self._delete_min(node.left)
            node = self._restore(node)
            return node

    def _convert_left(self, node):
        if self._is_2node(node.left):
            if self._is_2node(node.right):
                self._flip_colors(node)
            elif self._is_34node(node.right):
                x = node.right.left
                node.right.left = x.right
                x.left, x.right, node.right = node, node.right, x.left
                x.color = node.color
                node.color = Color.BLACK
                node.left.color = Color.RED
                x.right.count = (self._size(x.right.left) +
                                 self._size(x.right.right) + 1)
                node = x
        return node

    def _restore(self, node):
        if self._is_red(node.right) and not self._is_red(node.left):
            node = self._rotate_left(node)
        if self._is_red(node.left) and self._is_red(node.left.left):
            node = self._rotate_right(node)
        if self._is_red(node.left) and self._is_red(node.right):
            node = self._flip_colors(node)

        node.count = self._size(node.left) + self._size(node.right) + 1
        return node

    def _is_balanced(self, node):
        def depth(node):
            if node is None:
                return 0
            left = depth(node.left)
            right = depth(node.right)
            if left != right:
                raise Exception('unbalanced')
            if self._is_black(node):
                return 1 + left
            else:
                return left

        if node is None:
            return True

        try:
            left = depth(node.left)
            right = depth(node.right)
            return left == right
        except Exception:
            return False

    @property
    def size(self):
        return self._size(self.root)

    def _size(self, node):
        if node is None:
            return 0
        else:
            return node.count

    @property
    def max(self):
        if self.root is None:
            raise ValueError('max on empty tree')
        return self._max(self.root)

    def _max(self, node):
        x = self._find_max(node)
        return x.key

    def _find_max(self, node):
        if node.right is None:
            return node
        else:
            return self._find_max(node.right)

    @property
    def min(self):
        if self.root is None:
            raise ValueError('min on empty tree')
        return self._min(self.root)

    def _min(self, node):
        x = self._find_min(node)
        return x.key

    def _find_min(self, node):
        if node.left is None:
            return node
        else:
            return self._find_min(node.left)

    def range(self, min_, max_):
        def _range(node):
            if node is None:
                return

            if node.key > max_:
                yield from _range(node.left)
            elif node.key < min_:
                yield from _range(node.right)
            else:
                yield from _range(node.left)
                yield node.key
                yield from _range(node.right)

        if min_ > max_:
            return
        yield from _range(self.root)


class BalancedBstSet:
    def __init__(self):
        self.bst = RedBlackBinarySearchTree()

    def add(self, key):
        self.bst.put(key)

    def __contains__(self, key):
        return key in self.bst

    def delete(self, key):
        self.bst.delete(key)

    def range(self, a, b):
        for k in self.bst.range(a, b):
            yield k

    @property
    def count(self):
        return self.bst.size

    def __str__(self):
        return str(self.bst.root)


def run():
    q = int(input())
    s = BalancedBstSet()

    for _ in range(q):
        command, *value = [int(x) for x in input().split()]
        if command == 0:
            s.add(value[0])
            print(s.count)
        elif command == 1:
            if value[0] in s:
                print(1)
            else:
                print(0)
        elif command == 2:
            s.delete(value[0])
        elif command == 3:
            for i in s.range(*value):
                print(i)
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	set_range_search
# CreatedDate:  2020-07-25 12:57:11 +0900
# LastModified: 2020-07-25 13:36:16 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    q = int(input())
    ans = set()
    for _ in range(q):
        s = list(map(int, input().split()))
        if s[0] == 0:
            ans.add(s[1])
            print(len(ans))
        elif s[0] == 1:
            if s[1] in ans:
                print(1)
            else:
                print(0)
        elif s[0] == 2:
            if s[1] in ans:
                ans.remove(s[1])
        else:
            if len(ans) > s[2] - s[1]:
                for i in range(s[1], s[2]+1):
                    if i in ans:
                        print(i)
            else:
                ans = sorted(ans)
                for a in ans:
                    if s[1] <= a and a <= s[2]:
                        print(a)
                ans = set(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
q = int(input())
s = []
rs = [] # for discretization

# download the input
for i in range(q):
    s.append(list(map(int, input().split())))
    if s[i][0] == 3:
        rs.append(s[i][1])
        rs.append(s[i][2])
    else:
        rs.append(s[i][1])

rs.append(10**9 + 1)
rs = sorted(list(set(rs)))
index = {rs[i]:i for i in range(len(rs))} # discretization
used = [False for i in range(len(rs) + 1)] # tag the elements in set
cnt = 0
for i in range(q):
    op, x = s[i][0], s[i][1]
    idx = index[x]
    if op == 0:
        if not used[idx]:
            cnt += 1
        used[idx] = True
        print(cnt)
    elif op == 1:
        print(+used[idx])
    elif op == 2:
        if used[idx]:
            cnt -= 1
        used[idx] = False
    else:
        l = idx
        r = index[s[i][2]]
        for j in range(l, r+1):
            if used[j]:
                print(rs[j])

Submission status: Accepted

Solution code:
S = set()

for _ in range(int(input())):
    order = tuple(map(int,input().split()))
    value = order[1]

    if order[0] == 0:
        S.add(value)
        print(len(S))
    elif order[0] == 1:
        if value in S:
            print(1)
        else:
            print(0)
    elif order[0] == 2:
        S.discard(value)
    else:
        if len(S) > order[2] - order[1]:
            for i in range(order[1],order[2]+1):
                if i in S:
                    print(i)
        else:
            tmp = sorted(S)
            for i in tmp:
                if order[1] <= i <= order[2]:
                    print(i)

Submission status: Accepted

Solution code:
# Solved by QBnewb
# Discretization
# off-line

q = int(input())
s = []
rs = [] # for discretization

# download the input
for i in range(q):
    s.append(list(map(int, input().split())))
    if s[i][0] == 3:
        rs.append(s[i][1])
        rs.append(s[i][2])
    else:
        rs.append(s[i][1])

rs.append(10**9 + 1)
rs = sorted(list(set(rs)))
index = {rs[i]:i for i in range(len(rs))} # discretization
used = [False for i in range(len(rs) + 1)] # tag the elements in set
cnt = 0
for i in range(q):
    op, x = s[i][0], s[i][1]
    idx = index[x]
    if op == 0:
        if not used[idx]:
            cnt += 1
        used[idx] = True
        print(cnt)
    elif op == 1:
        print(+used[idx])
    elif op == 2:
        if used[idx]:
            cnt -= 1
        used[idx] = False
    else:
        l = idx
        r = index[s[i][2]]
        for j in range(l, r+1):
            if used[j]:
                print(rs[j])

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right,insort_left
dict = {}
keytbl = []
cnt = 0
q = int(input())
for i in range(q):
    a = list(input().split())
    ki = int(a[1])
    if a[0] == "0":
        if ki not in dict:
            dict[ki] =1
            cnt += 1
            insort_left(keytbl,ki)
        elif dict[ki] == 0:
            dict[ki] = 1
            cnt += 1
        print(cnt)
    elif a[0] == "1":print(dict[ki] if ki in dict else 0)
    elif a[0] == "2":
        if ki in dict:
            cnt -= dict[ki]
            dict[ki] =0
    else:
        L = bisect_left(keytbl,int(a[1]))
        R = bisect_right(keytbl,int(a[2]),L)
        for j in range(L,R):
            if dict[keytbl[j]] == 1:print(keytbl[j])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Set - Set: Range Search
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_7_C&lang=jp

"""
from bisect import insort, bisect_right, bisect_left

class Multi_set:
    def __init__(self):
        self.total = 0
        self.ms = dict()
        self.lr = []

    def insert(self, x):
        if x in self.ms:
            if self.ms[x] == 0:
                self.ms[x] = 1
                self.total += 1
        else:
            self.total += 1
            self.ms[x] = 1
            insort(self.lr, x)
        print(self.total)

    def find(self, x):
        print(self.ms.get(x, 0))

    def delete(self, x):
        if x in self.ms:
            self.total -= self.ms[x]
            self.ms[x] = 0

    def dump(self, l, r):
        lb = bisect_left(self.lr, l)
        ub = bisect_right(self.lr, r)
        for i in range(lb, ub):
            k = self.lr[i]
            v = self.ms[k]
            print(f'{k}\n' * v, end='')


ms = Multi_set()
for _ in range(int(input())):
    op, x, y = (input() + ' 1').split()[:3]
    if op == '0':
        ms.insert(int(x))
    elif op == '1':
        ms.find(int(x))
    elif op == '2':
        ms.delete(int(x))
    else:
        ms.dump(int(x), int(y))

Submission status: Accepted

Solution code:
q = int(input())
S = set()

for i in range(q):
    query = input()

    # insert
    if query[0] == "0":
        _, x = list(map(int, query.split()))
        S.add(x)
        print(len(S))

    # find
    elif query[0] == "1":
        _, x = list(map(int, query.split()))
        if x in S:
            print(1)
        else:
            print(0)

    # delete
    elif query[0] == "2":
        _, x = list(map(int, query.split()))
        S.discard(x)

    # dump
    else:
        _, L, R = list(map(int, query.split()))
        
        if len(S) > (R - L):
            for i in range(L, R + 1):
                if i in S:
                    print(i)
        else:
            answer = []
            for SItem in S:
                if L <= SItem <= R:
                    answer.append(SItem)

            [print(answerItem) for answerItem in sorted(answer)]

Submission status: Accepted

Solution code:
import sys

s = set()
input()

for q in sys.stdin:
    q = q.split()
    if q[0] == '0':
        s.add(int(q[1]))
        print(len(s))
    elif q[0] == '1':
        print(int(int(q[1]) in s))
    elif q[0] == '2':
        s.discard(int(q[1]))
    else:
        ans = []
        if len(s) > int(q[2]) - int(q[1]):
            for i in range(int(q[1]), int(q[2])+1):
                if i in s:
                    print(i)
        else:
            for i in s:
                if int(q[1]) <= i <= int(q[2]):
                    ans.append(i)
    
            for i in sorted(ans):
                print(i)

Submission status: Accepted

Solution code:
def main():

    q = int(input())
    s = set()

    for _ in range(q):
        para = [int(a) for a in input().split()]

        if para[0] == 0:
            s.add(para[1])
            print(len(s))
        elif para[0] == 1:
            if para[1] in s:
                print("1")
            else:
                print("0")
        elif para[0] == 2:
            s.discard(para[1])
        elif para[0] == 3:

            if len(s) > (para[2] - para[1]):
                for i in range(para[1], para[2] + 1):
                    if i in s:
                        print(i)
            else:
                s = sorted(s)
                for e in s:
                    if para[1] <= e <= para[2]:
                        print(e)
                s = set(s)
main()

Submission status: Accepted

Solution code:
import bisect

S=[]

q=int(input())

def find(x):
    index=bisect.bisect_left(S,x)
    if index==len(S):
        return False
    return S[index]==x


for _ in range(q):
    query=[int(i) for i in input().split(" ")]
    if query[0]==0:
        if find(query[1]):
            pass
        else:
            bisect.insort_left(S, query[1])
        print(len(S))
    elif query[0]==1:
        if find(query[1]):
            print(1)
        else:
            print(0)
    elif query[0]==2:
        if find(query[1]):
            S.remove(query[1])
    else:
        L,R=query[1],query[2]
        indL=bisect.bisect_left(S,L)
        indR=bisect.bisect_right(S,R)
        for s in S[indL:indR]:
            print(s)

Submission status: Accepted

Solution code:
from bisect import insort, bisect_right, bisect_left


class IntSet:
    def __init__(self) -> None:
        self.total = 0
        self.ms: dict = dict()
        self.lr: list = []

    def insert(self, x: int) -> None:
        if x in self.ms:
            if self.ms[x] == 0:
                self.ms[x] = 1
                self.total += 1
        else:
            self.total += 1
            self.ms[x] = 1
            insort(self.lr, x)
        print(self.total)

    def find(self, x: int) -> None:
        print(self.ms.get(x, 0))

    def delete(self, x: int) -> None:
        if x in self.ms:
            self.total -= self.ms[x]
            self.ms[x] = 0

    def dump(self, l: int, r: int) -> None:
        lb = bisect_left(self.lr, l)
        ub = bisect_right(self.lr, r)
        for i in range(lb, ub):
            k = self.lr[i]
            v = self.ms[k]
            print(f'{k}\n' * v, end='')


if __name__ == "__main__":
    ms = IntSet()
    num_query = int(input())
    for _ in range(num_query):
        op, *v = map(lambda x: int(x), input().split())
        if 0 == op:
            ms.insert(v[0])
        elif 1 == op:
            ms.find(v[0])
        elif 2 == op:
            ms.delete(v[0])
        else:
            ms.dump(v[0], v[1])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, insort_left
dict = {}
keytbl = []
cnt = 0
q = int(input())
for i in range(q):
	a = list(input().split())
	ki = int(a[1])
	if a[0] == '0':
		if ki not in dict:
			dict[ki] = 1
			cnt += 1
			insort_left(keytbl, ki)
		elif dict[ki] == 0:
			dict[ki] = 1
			cnt += 1
		print(cnt)
	elif a[0] == '1': print(dict[ki] if ki in dict else 0)
	elif a[0] == '2':
		if ki in dict:
			cnt -= dict[ki]
			dict[ki] = 0
	else:
		L = bisect_left (keytbl, int(a[1]))
		R = bisect_right(keytbl, int(a[2]), L)
		for j in range(L, R):
			if dict[keytbl[j]] == 1: print(keytbl[j])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Set - Set: Range Search
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_7_C&lang=jp

"""
from bisect import insort, bisect_right, bisect_left

class Multi_set:
    def __init__(self):
        self.total = 0
        self.ms = dict()
        self.lr = []

    def insert(self, x):
        if x in self.ms:
            if self.ms[x] == 0:
                self.ms[x] = 1
                self.total += 1
        else:
            self.total += 1
            self.ms[x] = 1
            insort(self.lr, x)
        print(self.total)

    def find(self, x):
        print(self.ms.get(x, 0))

    def delete(self, x):
        if x in self.ms:
            self.total -= self.ms[x]
            self.ms[x] = 0

    def dump(self, l, r):
        lb = bisect_left(self.lr, l)
        ub = bisect_right(self.lr, r)
        for i in range(lb, ub):
            k = self.lr[i]
            v = self.ms[k]
            print(f'{k}\n' * v, end='')


ms = Multi_set()
for _ in range(int(input())):
    op, x, y = (input() + ' 1').split()[:3]
    if op == '0':
        ms.insert(int(x))
    elif op == '1':
        ms.find(int(x))
    elif op == '2':
        ms.delete(int(x))
    else:
        ms.dump(int(x), int(y))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, insort_left

q = int(input())
S = []
D = {}
a = []
c = 0
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        if not a[i][1] in D:
            insort_left(S,a[i][1])
            D[a[i][1]] = 1
            c += 1
        else:
            if not D[a[i][1]] == 1:
                D[a[i][1]] = 1
                c += 1
        print(c)
    elif a[i][0] == 1:
        if a[i][1] in D:
            if D[a[i][1]] == 1:
                print(1)
            else:
                print(0)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in D:
            if D[a[i][1]] == 1:
                D[a[i][1]] = 0
                c -= 1
    else:
        L = bisect_left(S,a[i][1])
        R = bisect_right(S,a[i][2])
        for j in range(L,R):
            if D[S[j]] == 1:
                print(S[j])

Submission status: Accepted

Solution code:
import bisect


q = int(input())

S = []


for _ in range(q):

    command, *list_num = input().split()
    x = int(list_num[0])

    index = bisect.bisect_left(S, x)

    if   command == "0":
        # insert(x)
        x = int(list_num[0])
        if ((index == len(S)) or
            (S[index] != x)):
            S.insert(index, x)
        print(len(S))
    elif command == "1":
        # find(x)
        x = int(list_num[0])
        if ((index < len(S)) and
            (S[index] == x)):
            print(1)
        else:
            print(0)
    elif command == "2":
        # delete(x)
        x = int(list_num[0])
        if ((index < len(S)) and
            (S[index] == x)):
            del S[index]
    elif command == "3":
        # dump(L, R)
        L = x
        R = int(list_num[1])

        index_left = bisect.bisect_left(S, L)
        index_right = bisect.bisect_right(S, R)
        
        for element in S[index_left:index_right]:
            print(element)
    else:
        raise

Submission status: Accepted

Solution code:
from bisect import *
import sys
n = int(input())
ss = []
color = {}
cnt = 0
for _ in range(n):
    a, b, *c = map(int,sys.stdin.readline().split())
    if a == 0:
        if b not in color:
            insort_left(ss,b)
            color[b]=1
            cnt += 1
        elif color[b] == 0:
            color[b] = 1
            cnt += 1
        print(cnt)
    elif a == 1:
        print(color[b] if b in color else 0)
    elif a == 2:
        if b in color:
            cnt -=color[b]
            color[b] = 0
    else:
        L = bisect_left(ss,b)
        R = bisect(ss,c[0])
        for i in range(L,R):
            if color[ss[i]] == 1:
                print(ss[i])

Submission status: Accepted

Solution code:
import bisect

S=[]

def insert(S,count,x):
    y=bisect.bisect_left(S,x)
    if y>=count or S[y]!=x:
        S.insert(y,x)
        count+=1
    print(count)
    return S,count

def find(S,x):
    y=bisect.bisect_left(S,x)
    if y<count and S[y]==x:
        judge=1
    else:
        judge=0
    return judge,y

def erase(S,count,x):
    judge,y=find(S,x)
    if judge==1:
        S.pop(y)
        count-=1
    return S,count

def dump(S,L,R):
    s=bisect.bisect_left(S,L)
    e=bisect.bisect_right(S,R)
    if e-s>0:
        print('\n'.join(map(str,S[s:e])))

q=int(input())
count=0
for i in range(q):
    query=list(map(int,input().split()))
    
    if query[0]==0:
        S,count=insert(S,count,query[1])
    elif query[0]==1:
        print(find(S,query[1])[0])
    elif query[0]==2:
        S,count=erase(S,count,query[1])
    else:
        dump(S,query[1],query[2])

Submission status: Accepted

Solution code:
import sys
import bisect
nq = int(input())
lines = sys.stdin.readlines()
ans = [None] * nq
arr = []
for i in range(nq):
    q, *arg = lines[i].split()
    x = int(arg[0])
    idx = bisect.bisect_left(arr,x)
    if q == '0':    # insert x
        if idx == len(arr) or arr[idx] != x:
            arr.insert(idx, x)
        ans[i] = str(len(arr))
    elif q == '1':   # find x
        ans[i] = '1' if idx < len(arr) and arr[idx] == x else '0'
    elif q == '2':           # delete x
        if idx < len(arr) and arr[idx] == x:
            del arr[idx]
    else:                   # dump L R
        l_idx = bisect.bisect_left(arr, x)
        r_idx = bisect.bisect_right(arr, int(arg[1]))
        ans[i] = '\n'.join(map(str, arr[l_idx:r_idx]))
    #print(q, *arg, '\t', arr)

[print(x) for x in ans if x]