8818: [yosupo] Data Structure - Predecessor Problem
[Creator : ]
Description
Let $S$ be a set consisting of integers between $0$ to $N-1$. Process the following $Q$ queries:
- 0 $k$ : If $k\notin S$, insert $k$ into $S$. If $k\in S$, do nothing.
- 1 $k$ : If $k\in S$, remove $k$ from $S$. If $k\notin S$, do nothing.
- 2 $k$ : if $S$ contains $k$, print $1$. Otherwise, print $0$.
- 3 $k$ : Print the smallest key which is greater than or equal to $k$(if there are no keys, print $-1$).
- 4 $k$ : Print the largest key which is smaller than or equal to $k$(if there are no keys, print $-1$).
- 0 $k$ : If $k\notin S$, insert $k$ into $S$. If $k\in S$, do nothing.
- 1 $k$ : If $k\in S$, remove $k$ from $S$. If $k\notin S$, do nothing.
- 2 $k$ : if $S$ contains $k$, print $1$. Otherwise, print $0$.
- 3 $k$ : Print the smallest key which is greater than or equal to $k$(if there are no keys, print $-1$).
- 4 $k$ : Print the largest key which is smaller than or equal to $k$(if there are no keys, print $-1$).
Input
The initial state of $S$ is given as a length $N$ string $T$ consisting of $0$ and $1$. $S$ contains $i$ if and only if $T_i = 1$.
$N\ Q$
$T$
$c_0\ k_0$
$c_1\ k_1$
$\vdots$
$c_{Q-1}\ k_{Q-1}$
$N\ Q$
$T$
$c_0\ k_0$
$c_1\ k_1$
$\vdots$
$c_{Q-1}\ k_{Q-1}$
Constraints
$1 \leq N \leq 10^7$
$1 \leq Q \leq 10^6$
$0 \leq k_i \lt N$
$1 \leq Q \leq 10^6$
$0 \leq k_i \lt N$
Sample 1 Input
6 9
010101
3 3
4 3
4 0
0 4
1 3
2 4
2 3
3 3
4 3
Sample 1 Output
3
3
-1
1
0
4
1