C 数列之和
- 数列 $a$ 由 $10^{100}$ 项组成，从第一项开始有 $a_i = 2i - 2$。
- 将数列 $a$ 中所有长度大于 $1$ 的连续子数列的元素和去重后从小到大构成一个新的数列，求这个数列的第 $k$ 项。
注意到，答案为 $2(k + \lfloor \log_2{(k + \lfloor \log_2 k \rfloor)} \rfloor)$，时间复杂度 $\mathcal O(T)$。
首先，需要特判 $c_i = c_j$ 但 $d_i \neq d_j$ 的情形，此时答案为 $0$。
否则，我们可以把每相邻的两条一元限制作为一个区间单独拎出来。这样做正确的原因是，每一个 $x_i$ 的取值只受前面一个数的影响。事实上，完全可以任意选取区间，只不过这样选可以利用已知的 $x_i$，依次讨论出 $a_{i+1}, b_{i+1}, a_{i+2}, b_{i+2}, \cdots$ 的可能取值，便于计算答案。
我们随便找几个数举个例子：
题目中出现了至多和最小等字眼，因此很有可能需要使用二分答案。
怎么进行二分呢？我们对 $d$ 进行二分并检验当前 $d$ 值是否符合题意。不难发现，如果一个点到原点的距离不超过 $d$，那么这个点一定符合（所有正比例函数都经过原点）。因此我们只需考虑 $x^2+y^2 \gt d^2$ 的点。