Balance (Hard version) (Codeforces 1732D2)
Tags: Others, number theory

This is the hard version of the problem. The only difference is that in this version there are remove queries.Initially you have a set containing one element — $$$0$$$. You need to handle $$$q$$$ queries of the following types:+ $$$x$$$ — add the integer $$$x$$$ to the set. It is guaranteed that this integer is not contained in the set; - $$$x$$$ — remove the integer $$$x$$$ from the set. It is guaranteed that this integer is contained in the set; ? $$$k$$$ — find the $$$k\text{-mex}$$$ of the set. In our problem, we define the $$$k\text{-mex}$$$ of a set of integers as the smallest non-negative integer $$$x$$$ that is divisible by $$$k$$$ and which is not contained in the set.

Input: The first line contains an integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.The following $$$q$$$ lines describe the queries.An addition query of integer $$$x$$$ is given in the format + $$$x$$$ ($$$1 \leq x \leq 10^{18}$$$). It is guaranteed that $$$x$$$ is not contained in the set.A remove query of integer $$$x$$$ is given in the format - $$$x$$$ ($$$1 \leq x \leq 10^{18}$$$). It is guaranteed that $$$x$$$ is contained in the set.A search query of $$$k\text{-mex}$$$ is given in the format ? $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$).It is guaranteed that there is at least one query of type ?.

Output: For each query of type ? output a single integer — the $$$k\text{-mex}$$$ of the set.

Note: In the first example:After the first and second queries, the set will contain elements $$$\{0, 1, 2\}$$$. The smallest non-negative number that is divisible by $$$1$$$ and is not in the set is $$$3$$$.After the fourth query, the set will contain the elements $$$\{0, 1, 2, 4\}$$$. The smallest non-negative number that is divisible by $$$2$$$ and is not in the set is $$$6$$$.In the second example:  Initially, the set contains only the element $$$\{0\}$$$.  After adding an integer $$$100$$$ the set contains elements $$$\{0, 100\}$$$.  $$$100\text{-mex}$$$ of the set is $$$200$$$.  After adding an integer $$$200$$$ the set contains elements $$$\{0, 100, 200\}$$$.  $$$100\text{-mex}$$$ of the set $$$300$$$.  After removing an integer $$$100$$$ the set contains elements $$$\{0, 200\}$$$.  $$$100\text{-mex}$$$ of the set is $$$100$$$.  After adding an integer $$$50$$$ the set contains elements $$$\{0, 50, 200\}$$$.  $$$50\text{-mex}$$$ of the set is $$$100$$$.  After removing an integer $$$50$$$ the set contains elements $$$\{0, 200\}$$$.  $$$100\text{-mex}$$$ of the set is $$$50$$$. 

Sample Inputs:
18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
- 4
? 1
? 2

10
+ 100
? 100
+ 200
? 100
- 100
? 100
+ 50
? 50
- 50
? 50

Sample Outputs:
3
6
3
3
10
3
2000000000000000000
3
4

200
300
100
100
50

Solution (Python):
import copy
from collections import defaultdict as dd
from collections import deque
import math
import sys
import os
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
local_run = False
if os.environ.get('PYTHON_CONTEST_HELPER'):
    local_run = True

    def print_details_helper(q):
        out = []
        for (k, x) in enumerate(q):
            out.append(f'\n\t{k}:\t{x}')
        return ''.join(out) + '\n'
    pdh = print_details_helper

    def print_tsv_helper(q):
        out = []
        for row in q:
            out.append('\t'.join((str(x) for x in row)))
        return ''.join(('\n\t' + x for x in out)) + '\n'
    pth = print_tsv_helper
    OUT_RED_BOLD = '\x1b[31;1m'
    OUT_GREEN = '\x1b[32m'
    OUT_RESET = '\x1b[0m'
    OUT_BOLD = '\x1b[;1m'
    OUT_RED = '\x1b[31m'
    OUT_WHITE = '\x1b[97m'
    OUT_BLUE = '\x1b[34;1m'
    OUT_CYAN = '\x1b[36;1m'
    OUT_PURPLE = '\x1b[35;1m'
    OUT_YELLOW = '\x1b[33;1m'
    OUT_BACKGROUND = '\x1b[41;30m'

    def flush_stdout():
        print('', flush=True, end='')

    def dbgBase(*args, **kwargs):
        flush_stdout()
        color_helper = kwargs.pop('color', OUT_CYAN)
        if kwargs.get('comment_first', False):
            print(f'{OUT_BOLD}{color_helper}{args[0]: >11} {OUT_RESET}', end='', file=sys.stderr)
            args = tuple(args[1:])
        else:
            print(f"{'': >12}", end='', file=sys.stderr)
        if 'comment_first' in kwargs:
            del kwargs['comment_first']
        print(f'{OUT_RED_BOLD}{sys._getframe().f_back.f_back.f_lineno: >7} {OUT_BOLD}:  {OUT_RESET}{color_helper}', end='', file=sys.stderr)
        end_maybe = kwargs.get('end', '\n')
        kwargs['end'] = f'{OUT_RESET}{end_maybe}'
        if 'sep' not in kwargs:
            kwargs['sep'] = ' ' * 3
        kwargs['flush'] = True
        print(*args, file=sys.stderr, **kwargs)

    def dbg(*args, **kwargs):
        dbgBase(*args, color=OUT_CYAN, **kwargs)

    def dbgG(*args, **kwargs):
        dbgBase(*args, color=OUT_GREEN, **kwargs)

    def dbgP(*args, **kwargs):
        dbgBase(*args, color=OUT_PURPLE, **kwargs)

    def dbgY(*args, **kwargs):
        dbgBase(*args, color=OUT_YELLOW, **kwargs)

    def dbgR(*args, **kwargs):
        dbgBase(*args, color=OUT_RED, **kwargs)

    def dbgB(*args, **kwargs):
        dbgBase(*args, color=OUT_BLUE, **kwargs)

    def dbgW(*args, **kwargs):
        dbgBase(*args, color=OUT_WHITE, **kwargs)

    def dbgBackground(*args, **kwargs):
        dbgBase(*args, color=OUT_BACKGROUND, **kwargs)

    def el(n=1):
        flush_stdout()
        print('\n' * n, file=sys.stderr, end='', flush=True)

    def dbgc(*args, **kwargs):
        dbgBase(*args, comment_first=True, color=OUT_CYAN, **kwargs)

    def dbgcG(*args, **kwargs):
        dbgBase(*args, comment_first=True, color=OUT_GREEN, **kwargs)

    def dbgcP(*args, **kwargs):
        dbgBase(*args, comment_first=True, color=OUT_PURPLE, **kwargs)

    def dbgcY(*args, **kwargs):
        dbgBase(*args, comment_first=True, color=OUT_YELLOW, **kwargs)

    def dbgcR(*args, **kwargs):
        dbgBase(*args, comment_first=True, color=OUT_RED, **kwargs)

    def dbgcB(*args, **kwargs):
        dbgBase(*args, comment_first=True, color=OUT_BLUE, **kwargs)

    def dbgcW(*args, **kwargs):
        dbgBase(*args, comment_first=True, color=OUT_WHITE, **kwargs)

    def dbgcBackground(*args, **kwargs):
        dbgBase(*args, comment_first=True, color=OUT_BACKGROUND, **kwargs)
else:

    def dbg(*args, **kwargs):
        pass

    def dbgG(*args, **kwargs):
        pass

    def dbgP(*args, **kwargs):
        pass

    def dbgY(*args, **kwargs):
        pass

    def dbgR(*args, **kwargs):
        pass

    def dbgB(*args, **kwargs):
        pass

    def dbgW(*args, **kwargs):
        pass

    def dbgBackground(*args, **kwargs):
        pass

    def dbgc(*args, **kwargs):
        pass

    def dbgcG(*args, **kwargs):
        pass

    def dbgcP(*args, **kwargs):
        pass

    def dbgcY(*args, **kwargs):
        pass

    def dbgcR(*args, **kwargs):
        pass

    def dbgcB(*args, **kwargs):
        pass

    def dbgcW(*args, **kwargs):
        pass

    def dbgcBackground(*args, **kwargs):
        pass

    def el(n=1):
        pass

    def print_details_helper(*args, **kwargs):
        pass

    def print_tsv_helper(*args, **kwargs):
        pass

    def pdh(*args, **kwargs):
        pass

    def pth(*args, **kwargs):
        pass
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def nn():
    return int(input())

def li():
    return list(input())

def lm():
    return list(map(int, input().split()))

def solve(testID):
    N = nn()
    dat = []
    for _ in range(N):
        dat.append(input().split(' '))
    dbg(N, dat)
    main_set = set()
    removed_sets = dd(set)
    connected_vals = dd(set)
    memoized_vals = dd(int)
    for (op, num) in dat:
        dbgG(op, num)
        x = int(num)
        if op == '+':
            main_set.add(x)
            for y in connected_vals[x]:
                removed_sets[y].remove(x)
        elif op == '-':
            main_set.remove(x)
            for y in connected_vals[x]:
                removed_sets[y].add(x)
        elif len(removed_sets[x]) > 0:
            print(min(removed_sets[x]))
        else:
            curr_val = max(memoized_vals[x], x)
            while curr_val in main_set:
                connected_vals[curr_val].add(x)
                curr_val += x
            memoized_vals[x] = curr_val
            print(curr_val)
    return
if __name__ == '__main__':
    T = 1
    for testID in range(1, T + 1):
        el()
        dbgBackground(f'Case {testID}')
        solve(testID)

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
s = set()
nxt = {}
dele = {}
fac = {}
for _ in range(int(input())):
    (op, x) = input().split()
    x = int(x)
    if op == '+':
        s.add(x)
    elif op == '-':
        s.remove(x)
        for y in fac.get(x, []):
            if x % y == 0 and x // y < nxt[y]:
                dele.setdefault(y, [])
                heapq.heappush(dele[y], x // y)
    else:
        i = nxt.get(x, 1)
        dels = dele.get(x, [])
        while dels and dels[0] < i and (dels[0] * x in s):
            heapq.heappop(dels)
        if dels:
            i = dels[0]
        else:
            while i * x in s:
                fac.setdefault(i * x, [])
                fac[i * x].append(x)
                i += 1
            nxt[x] = i
        print(i * x)

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
s = set()
nxt = {}
dele = {}
fac = {}
for _ in range(int(input())):
    (op, x) = input().split()
    x = int(x)
    if op == '+':
        s.add(x)
    elif op == '-':
        s.remove(x)
        for y in fac.get(x, []):
            if x % y == 0 and x // y < nxt[y]:
                dele.setdefault(y, [])
                heapq.heappush(dele[y], x // y)
    else:
        i = nxt.get(x, 1)
        dels = dele.get(x, [])
        while dels and dels[0] < i and (dels[0] * x in s):
            heapq.heappop(dels)
        if dels:
            i = dels[0]
        else:
            while i * x in s:
                fac.setdefault(i * x, [])
                fac[i * x].append(x)
                i += 1
            nxt[x] = i
        print(i * x)