問題一覧 > 教育的問題

No.3581 Fractional Symmetric Difference Update and Range Count Query

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : 👑 p-adic
お気に入りにしたユーザー ProblemId : 9439 / 自分の提出
問題文最終更新日: 2026-07-03 12:12:52
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 503 (順位表) の他の問題:

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:

  1. 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 \}$)
  2. 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.
  3. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。