No.3581 Fractional Symmetric Difference Update and Range Count Query
タグ : / 解いたユーザー数 12
作問者 : 👑
Problem Statement
The time limit for this problem is 10000[ms].
Problem Statement
First, a positive integer $Q$ is given.
A set $S$ is initially given as the empty set.
Process the $Q$ queries described below in the given order.
Each query is a tuple $(i,L,R)$ of $3$ positive integers $i, L, R$ satisfying $L \leq R$.
A query $(i,L,R)$ is processed as follows:
- First, let $T$ be the set of all positive integers that can be expressed as $\lfloor \frac{i}{d} \rfloor$ using some positive integer $d$ less than or equal to $i$. ($T = \{\lfloor \frac{i}{d} \rfloor \mid d \in \mathbb{N} \cap [1,i]\} = \{\lfloor \frac{i}{1} \rfloor, \ldots, \lfloor \frac{i}{i} \rfloor \}$)
- Next, for each element $j$ of $T$, update $S$ by removing $j$ from $S$ if $j$ is an element of $S$, and inserting $j$ into $S$ otherwise.
- Finally, for the updated $S$, find the number of elements $j$ of $S$ satisfying $L \leq j \leq R$. (Hereafter, this value is called the answer to this query.)
Here, for a real number $x$, $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$.
Input
For each positive integer $q$ less than or equal to $Q$, let the $q$-th query be $(i_q,L_q,R_q)$.
Then, the input is given from standard input in $1 + Q$ lines in the following format:
- Line $1$ contains $Q$, separated by half-width spaces.
- For each positive integer $q$ less than or equal to $Q$, line $1 + q$ contains $i_q,L_q,R_q$, separated by half-width spaces.
$Q$ $i_1$ $L_1$ $R_1$ $\vdots$ $i_Q$ $L_Q$ $R_Q$
Constraints
The input satisfies the following constraints:
- $Q$ is an integer satisfying $1 \leq Q \leq 10^5$.
- For every positive integer $q$ less than or equal to $Q$,
- $i_q$ is an integer satisfying $1 \leq i_q \leq 10^6$.
- $L_q,R_q$ are integers satisfying $1 \leq L_q \leq R_q \leq 10^6$.
Output
For each positive integer $q$ less than or equal to $Q$, output the answer to the $q$-th query on line $q$.
($1$ 個目のクエリに対する回答) $\vdots$ ($Q$ 個目のクエリに対する回答)
Print a newline at the end.
Sample
Sample 1
Input
5 5 1 5 4 2 5 3 3 5 2 4 5 1 5 5
Output
3 2 3 2 1
Initially, $S$ is given as the empty set $\{\}$.
Process the $1$st query $(i_1,L_1,R_1) = (5,1,5)$. First,
$\displaystyle \begin{array}{rcl} \displaystyle T &\displaystyle = &\displaystyle \left\{\left\lfloor \frac{i_1}{d} \right\rfloor \middle| d \in \mathbb{N} \cap [1,i_1]\right\} \\ & & \\ \displaystyle &\displaystyle = &\displaystyle \left\{\left\lfloor \frac{5}{1} \right\rfloor, \left\lfloor \frac{5}{2} \right\rfloor, \left\lfloor \frac{5}{3} \right\rfloor, \left\lfloor \frac{5}{4} \right\rfloor, \left\lfloor \frac{5}{5} \right\rfloor \right\} \\ & & \\ \displaystyle &\displaystyle = &\displaystyle \{5, 2, 1, 1, 1 \} \\ \displaystyle &\displaystyle = &\displaystyle \{1,2,5 \} \end{array} $
holds. Next, since $1,2,5 \notin S$, $S$ is replaced by
$\displaystyle S \cup \{1,2,5 \} = \{1,2,5 \} $
. For the updated $S$, we have
$\displaystyle S \cap [L_1,R_1] = \{1,2,5\} \cap [1,5] = \{1,2,5 \} $
and the number of its elements is $3$.
Process the $2$nd query $(i_2,L_2,R_2) = (4,2,5)$. First,
$\displaystyle \begin{array}{rcl} \displaystyle T &\displaystyle = &\displaystyle \left\{\left\lfloor \frac{i_2}{d} \right\rfloor \middle| d \in \mathbb{N} \cap [1,i_2]\right\} \\ & & \\ \displaystyle &\displaystyle = &\displaystyle \left\{\left\lfloor \frac{4}{1} \right\rfloor, \left\lfloor \frac{4}{2} \right\rfloor, \left\lfloor \frac{4}{3} \right\rfloor, \left\lfloor \frac{4}{4} \right\rfloor \right\} \\ & & \\ \displaystyle &\displaystyle = &\displaystyle \{4, 2, 1 \} \\ \displaystyle &\displaystyle = &\displaystyle \{1,2,4 \} \end{array} $
holds. Next, since $1,2 \in S$ and $4 \notin S$, $S$ is replaced by
$\displaystyle (S \setminus \{1,2\}) \cup \{4 \} = \{4,5 \} $
. For the updated $S$, we have
$\displaystyle S \cap [L_2,R_2] = \{4,5\} \cap [2,5] = \{4,5 \} $
and the number of its elements is $2$.
Process the $3$rd query $(i_3,L_3,R_3) = (3,3,5)$. First,
$\displaystyle \begin{array}{rcl} \displaystyle T &\displaystyle = &\displaystyle \left\{\left\lfloor \frac{i_3}{d} \right\rfloor \middle| d \in \mathbb{N} \cap [1,i_3]\right\} \\ & & \\ \displaystyle &\displaystyle = &\displaystyle \left\{\left\lfloor \frac{3}{1} \right\rfloor, \left\lfloor \frac{3}{2} \right\rfloor, \left\lfloor \frac{3}{3} \right\rfloor \right\} \\ & & \\ \displaystyle &\displaystyle = &\displaystyle \{3, 1, 1 \} \\ \displaystyle &\displaystyle = &\displaystyle \{1,3 \} \end{array} $
holds. Next, since $1,3 \notin S$, $S$ is replaced by
$\displaystyle S \cup \{1,3 \} = \{1,3,4,5 \} $
. For the updated $S$, we have
$\displaystyle S \cap [L_3,R_3] = \{1,3,4,5\} \cap [3,5] = \{3,4,5 \} $
and the number of its elements is $3$.
Process the $4$th query $(i_4,L_4,R_4) = (2,4,5)$. First,
$\displaystyle \begin{array}{rcl} \displaystyle T &\displaystyle = &\displaystyle \left\{\left\lfloor \frac{i_4}{d} \right\rfloor \middle| d \in \mathbb{N} \cap [1,i_4]\right\} \\ & & \\ \displaystyle &\displaystyle = &\displaystyle \left\{\left\lfloor \frac{2}{1} \right\rfloor, \left\lfloor \frac{2}{2} \right\rfloor \right\} \\ & & \\ \displaystyle &\displaystyle = &\displaystyle \{2, 1 \} \\ \displaystyle &\displaystyle = &\displaystyle \{1,2 \} \end{array} $
holds. Next, since $1 \in S$ and $2 \notin S$, $S$ is replaced by
$\displaystyle (S \setminus \{1\}) \cup \{2 \} = \{2,3,4,5 \} $
. For the updated $S$, we have
$\displaystyle S \cap [L_4,R_4] = \{2,3,4,5\} \cap [4,5] = \{4,5 \} $
and the number of its elements is $2$.
Process the $5$th query $(i_5,L_5,R_5) = (1,5,5)$. First,
$\displaystyle \begin{array}{rcl} \displaystyle T &\displaystyle = &\displaystyle \left\{\left\lfloor \frac{i_5}{d} \right\rfloor \middle| d \in \mathbb{N} \cap [1,i_5]\right\} \\ & & \\ \displaystyle &\displaystyle = &\displaystyle \left\{\left\lfloor \frac{1}{1} \right\rfloor \right\} \\ & & \\ \displaystyle &\displaystyle = &\displaystyle \{1 \} \end{array} $
holds. Next, since $1 \notin S$, $S$ is replaced by
$\displaystyle S \cup \{1 \} = \{1,2,3,4,5 \} $
. For the updated $S$, we have
$\displaystyle S \cap [L_5,R_5] = \{1,2,3,4,5\} \cap [5,5] = \{5 \} $
and the number of its elements is $1$.
Since $Q = 5$ in this case, all processing ends here.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。