J2-超大序列
让 ( K ) 是所需的答案。
让我们记 ( sumA = \sum_{i=1}^N A_i )。
({B_1, \ldots, B_K}) 是 ( A ) 的若干个（比如 ( p ) 个）副本的连接，后跟 ( A ) 的前几个（比如 ( q ) 个）项。
这里，我们假设 ( p \geq 0, 1 \leq q \leq N )。
现在让我们找到 ( p ) 和 ( q )。
( p ) 可以通过
[p = \lfloor \frac{x}{sumA} \rfloor]
得到。
( q ) 可以通过朴素地求和 ( A_i ) 得到，计算时间为 ( O(N) )。
现在我们得到答案
[K = p \times N + q,]
因此问题已经解决。
J2-序列查询
我们称一个整数为好整数，如果它不同于 ( A_1, A_2, \ldots, A_N ) 中的任何一个。
对于每个 ( i )，找到小于或等于 ( A_i ) 的好整数的个数，并将其记录为 ( C_i )。
那么，第K小的好整数可以通过以下方式找到：
* 如果 ( C_N < K )
* 答案总是大于 ( A_N )。由于每个大于 ( A_N ) 的整数都是好整数，所以答案是 ( A_N + (K - C_N) )。
* 如果 ( C_N \geq K )
* 使用二分查找找到最小的 ( i ) 使得 ( C_i \geq K )，那么答案大于 ( A_{i-1} ) 且小于 ( A_i )（这里我们假设 ( A_0 = 0 )）。由于每个大于 ( A_{i-1} ) 且小于 ( A_i ) 的整数都是好整数，所以答案是 ( (A_i - 1) - (C_i - K) )，也就是说，在 ( A_i - 1 ) 之前的 ( C_i - K ) 个元素。
复杂度为 ( O(N + Q \log N) )。
J2-序列差值
首先，如果简单地比较所有配对，你需要计算所有 ( NM ) 对的差值。在本次约束条件下，这将需要 ( 4 \times 10^{10} ) 次计算，无法在时间限制内完成。
相反，我们首先对两个数组进行排序。通常，如果给定序列或集合的顺序无关紧要，通过排序使其单调有时可以使问题更容易解决。我们几乎总是可以对给定的大序列进行排序，而且如果问题可解，那么排序后数组的问题也应该可解，因此考虑这种情况没有任何缺点。
现在，我们假设数组已排序。即，我们假设 ( A_1 \leq A_2 \cdots \leq A_N ) 和 ( B_1 \leq B_2 \cdots \leq B_M )。然后，对于每个 ( i = 1, 2, \ldots, N )，按此顺序，我们将找到使 ( |A_i - B_j| ) 最小的 ( j )。如果 ( A_i \leq B_j )，那么对于任何 ( j < j' )，有 ( |A_i - B_j| = B_j - A_i \leq B_j - A_i = |A_i - B_j| )，因此我们不需要检查任何大于 ( j ) 的 ( j'
)。这看起来或多或少减少了计算量，但如果 ( A_i > B_N )，我们就必须检查每一对，所以这还不够。这里的关键在于反过来也很有用。即，如果 ( B_j \leq A_i < B_{j+1} )，那么对于每个 ( j' \leq j )，有 ( |A_{i+1} - B_j| = A_{i+1} - B_j \geq A_{i+1} - B_j \geq A_i - B_j = |A_i - B_j| )，因此我们不需要检查它。
总体而言，我们可以从 ( A_1 ) 和 ( B_1 ) 开始，重复以下步骤：
* 如果值 ( |A_i - B_j| ) 小于当前最小差值，则更新初步答案。
* 然后，比较 ( A_i ) 和 ( B_j )。
* 如果 ( A_i > B_j )，则将 ( B_j ) 更新为 ( B_{j+1} ) 并继续下一次迭代。
* 如果 ( A_i \leq B_j )，则我们不需要计算任何 ( j' > j ) 的 ( |A_i - B_j| )。此外，对于 ( A_{i+1} )，我们也不需要计算任何 ( j' < j ) 的 ( |A_{i+1} - B_j| )，因此我们继续使用 ( A_{i+1} ) 和 ( B_j ) 进行下一次迭代。
* 如果 ( i > N ) 且 ( j > M )，则终止操作。
现在让我们考虑上述步骤的复杂度。在每一步中，值 ( i + j ) 每次增加 1，因此迭代次数最多为 ( N + M - 1 )。由于每个操作可以在 ( O(1) ) 时间内完成，这部分可以在 ( O(N + M) ) 总时间内完成，因此加上初始排序，原问题可以在 ( O(N \log N + M \log M) ) 总时间内解决。
J2-子串询问
如果对每个查询都朴素地扫描 ( S_i, S_{i+1}, \ldots, S_n ) 来统计相同字母的出现次数，那么每个查询在最坏情况下需要 (\Theta(N)) 时间，对于 (Q) 个查询，最坏情况下总共需要 (\Theta(QN)) 时间，因此很难在时间限制内完成。
我们考虑一种更快响应每个查询的方法。假设查询给定一个子串 ( S_i, S_{i+1}, \ldots, S_n )，我们来思考如何找到答案。
基于给定的字符串 ( S )，定义一个长度为 ((N-1)) 的序列 ( A = (A_1, A_2, \ldots, A_{N-1}) )，其中：
[
A_i =
\begin{cases}
1 & \text{如果 } S_i = S_{i+1} \
0 & \text{如果 } S_i \neq S_{i+1}
\end{cases}
]
那么答案可以表示为 ( A_i + A_{i+1} + \cdots + A_{n-1} )。此外，我们定义一个序列 ( B = (B_0, B_1, B_2, \ldots, B_{N-1}) )：
[
B_i =
\begin{cases}
0 & \text{如果 } i = 0 \
A_1 + A_2 + \cdots + A_i & \text{如果 } i \geq 1
\end{cases}
]
这里，( B ) 是 ( A ) 的前缀和数组。那么，查询 ( A_i + A_{i+1} + \cdots + A_{n-1} ) 的答案等于：
[
A_i + A_{i+1} + \cdots + A_{n-1} = (A_1 + A_2 + \cdots + A_{n-1}) - (A_1 + A_2 + \cdots + A_{i-1}) = B_{n-1} - B_{i-1}
]
即 ( B ) 中两个元素的差：( B_{n-1} - B_{i-1} )。因此，如果我们预先计算 ( B )，那么每个查询的答案只需计算 ( B_{n-1} - B_{i-1} ) 即可在 ( O(1) ) 时间内得到。
因此，问题可以通过以下步骤在 ( O(N + Q) ) 总时间内解决：
* 首先针对输入的字符串 ( S ) 计算序列 ( A ) 及其前缀和数组 ( B )；
* 然后对于每个查询，以 ( O(1) ) 时间计算答案 ( B_{n-1} - B_{i-1} )。
注意，可以通过递推关系从序列 ( A ) 计算序列 ( B )，总时间为 ( O(N) )：
[
B_i =
\begin{cases}
0 & \text{如果 } i = 0 \
B_{i-1} + A_i & \text{如果 } i \geq 1
\end{cases}
]
