这是一篇模仿算导的学习笔记/题解。
例题：P1494
给定一个长为 \(n\) 的数组 \(a\) 和 \(m\) 个询问（有序数对）\(b_i = (l_i,r_i)\)，询问允许离线，对每个询问 \((l, r)\) 求出满足 \(l \le i \lt j \lt r \wedge a_i=a_j\) 的数对 \((i,j)\) 数量.
-
证明：若数 \(x\) 在 \(a\) 数组下标为 \([l, r)\) 的部分中出现次数为 \(c_x\)，则询问 \((l, r)\) 的答案为 $$\sum \limits_{c_x \ge 2} \dbinom{c_x}{2}$$
-
证明：\(\dbinom{x+1}{2}-\dbinom{x}{2}=x\).
-
若已知 \([l, r)\) 区间的 \(c_x\) 和答案，设计一种方法，在 \(\Theta(1)\) 的时间内得到 \([l, r+1)\)，\([l, r-1)\)，\([l-1, r)\)，\([l+1, r)\) 区间的相关信息。
-
对于询问 \(b_i\) 和 \(b_j\)，从 \(b_i\) 每次 \(\Theta(1)\) 移动端点到 \(b_j\) 的最坏复杂度是多少？对于 \(m\) 个询问，每次暴力移动的最坏总复杂度是多少？
-
若将 \(m\) 个询问按某个端点（\(l\) 或 \(r\)）排序，则最坏总复杂度是多少？
-
设计一种方法，在一个端点有序时使另一个端点相对集中。分析排序后暴力转移端点的时间复杂度。（提示：将这些询问分成 \(\lceil \dfrac{m}{B} \rceil\) 块，使每块内某个端点之差不超过 \(B\)）
-
\(B\) 取何值时，总复杂度最小？（提示：\(p,q\) 为正常数时 \(\dfrac{p}{x}+qx \ge 2 \sqrt{pq}\)，当且仅当 \(\dfrac{p}{x}=qx\) 时取等）