No.3581 分数対称差更新区間計数取得
p-adic問題文
この問題の実行時間制限は10000[ms]です。
問題文
最初に正整数 $Q$ が与えられます。
集合 $S$ が最初は空集合として与えられています。
以下で説明する $Q$ 個のクエリを与えられた順に処理してください。
各クエリは $L \leq R$ を満たす $3$ 個の正整数 $i, L, R$ の組 $(i,L,R)$ です。
クエリ $(i,L,R)$ は以下のように処理します：
- まず $i$ 以下のある正整数 $d$ を用いて $\lfloor \frac{i}{d} \rfloor$ と表せる正整数全体の集合を $T$ と置く。（$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 \}$）
- 次に $T$ の各要素 $j$ に対し、$j$ が $S$ の要素であるならば $S$ から $j$ を削除し、そうでないならば $S$ に $j$ を挿入することで $S$ を更新する。
- 最後に更新後の $S$ に対し $L \leq j \leq R$ を満たす $S$ の要素 $j$ の個数を求める。（以下、この値をこのクエリに対する回答と呼ぶ）
ただし実数 $x$ に対し $\lfloor x \rfloor$ で $x$ を超えない最大の整数を表します。
入力
$Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリを $(i_q,L_q,R_q)$ と置きます。
この時、入力は次の形式で標準入力から $1 + Q$ 行で与えられます：
- $1$ 行目に $Q$ が半角空白区切りで与えられます。
- $Q$ 以下の各正整数 $q$ に対し、$1 + q$ 行目に $i_q,L_q,R_q$ が半角空白区切りで与えられます。
$Q$ $i_1$ $L_1$ $R_1$ $\vdots$ $i_Q$ $L_Q$ $R_Q$
制約
入力は以下の制約を満たします：
- $Q$ は $1 \leq Q \leq 10^5$ を満たす整数である。
- $Q$ 以下の任意の正整数 $q$ に対し、
- $i_q$ は $1 \leq i_q \leq 10^6$ を満たす整数である。
- $L_q,R_q$ は $1 \leq L_q \leq R_q \leq 10^6$ を満たす整数である。
出力
$Q$ 以下の各正整数 $q$ に対し、$q$ 行目に $q$ 個目のクエリに対する回答を出力してください。
($1$ 個目のクエリに対する回答) $\vdots$ ($Q$ 個目のクエリに対する回答)
最後に改行してください。
サンプル
サンプル1
入力
5 5 1 5 4 2 5 3 3 5 2 4 5 1 5 5
出力
3 2 3 2 1
最初は $S$ が空集合 $\{\}$ として与えられています。
$1$ つ目のクエリ $(i_1,L_1,R_1) = (5,1,5)$ を処理します。まず
$\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} $
となります。次に $1,2,5 \notin S$ より $S$ が
$\displaystyle S \cup \{1,2,5 \} = \{1,2,5 \} $
に置き換わります。更新後の $S$ に対し
$\displaystyle S \cap [L_1,R_1] = \{1,2,5\} \cap [1,5] = \{1,2,5 \} $
であり、この要素数は $3$ です。
$2$ つ目のクエリ $(i_2,L_2,R_2) = (4,2,5)$ を処理します。まず
$\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} $
となります。次に $1,2 \in S$ かつ $4 \notin S$ より $S$ が
$\displaystyle (S \setminus \{1,2\}) \cup \{4 \} = \{4,5 \} $
に置き換わります。更新後の $S$ に対し
$\displaystyle S \cap [L_2,R_2] = \{4,5\} \cap [2,5] = \{4,5 \} $
であり、この要素数は $2$ です。
$3$ つ目のクエリ $(i_3,L_3,R_3) = (3,3,5)$ を処理します。まず
$\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} $
となります。次に $1,3 \notin S$ より $S$ が
$\displaystyle S \cup \{1,3 \} = \{1,3,4,5 \} $
に置き換わります。更新後の $S$ に対し
$\displaystyle S \cap [L_3,R_3] = \{1,3,4,5\} \cap [3,5] = \{3,4,5 \} $
であり、この要素数は $3$ です。
$4$ つ目のクエリ $(i_4,L_4,R_4) = (2,4,5)$ を処理します。まず
$\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} $
となります。次に $1 \in S$ かつ $2 \notin S$ より $S$ が
$\displaystyle (S \setminus \{1\}) \cup \{2 \} = \{2,3,4,5 \} $
に置き換わります。更新後の $S$ に対し
$\displaystyle S \cap [L_4,R_4] = \{2,3,4,5\} \cap [4,5] = \{4,5 \} $
であり、この要素数は $2$ です。
$5$ つ目のクエリ $(i_5,L_5,R_5) = (1,5,5)$ を処理します。まず
$\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} $
となります。次に $1 \notin S$ より $S$ が
$\displaystyle S \cup \{1 \} = \{1,2,3,4,5 \} $
に置き換わります。更新後の $S$ に対し
$\displaystyle S \cap [L_5,R_5] = \{1,2,3,4,5\} \cap [5,5] = \{5 \} $
であり、この要素数は $1$ です。
今回は $Q = 5$ であるため、これで全ての処理が終了します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。