CCF-CSP第24次认证第2题 --《序列查询新解》

4281. 序列查询新解 - AcWing题库

上一题“序列查询”中说道：

A=[A0,A1,A2,⋯,An]A=[A0,A1,A2,⋯,An] 是一个由 n+1n+1 个 [0,N)[0,N) 范围内整数组成的序列，满足 0=A0<A1<A2<⋯<An<N0=A0<A1<A2<⋯<An<N。

基于序列 AA，对于 [0,N)[0,N) 范围内任意的整数 xx，查询 f(x)f(x) 定义为：序列 AA 中小于等于 xx 的整数里最大的数的下标。

对于给定的序列 AA 和整数 xx，查询 f(x)f(x) 是一个很经典的问题，可以使用二分搜索在 O(logn)O(log⁡n) 的时间复杂度内轻松解决。

但在 IT 部门讨论如何实现这一功能时，小 P 同学提出了些新的想法。

小 P 同学认为，如果事先知道了序列 AA 中整数的分布情况，就能直接估计出其中小于等于 xx 的最大整数的大致位置。

接着从这一估计位置开始线性查找，锁定 f(x)。

如果估计得足够准确，线性查找的时间开销可能比二分查找算法更小。

比如说，如果 A1,A2,⋯,An 均匀分布在 (0,N)(0,N) 的区间，那么就可以估算出：

f(x)≈(n+1)⋅xN

为了方便计算，小 P 首先定义了比例系数 r=⌊Nn+1⌋，其中 ⌊ ⌋ 表示下取整，即r 等于 N 除以 n+1 的商。

进一步地，小 P 用 g(x)=⌊xr⌋ 表示自己估算出的 f(x)的大小，这里同样使用了下取整来保证 g(x)是一个整数。

显然，对于任意的询问 x∈[0,N)，g(x) 和 f(x)越接近则说明小 P 的估计越准确，后续进行线性查找的时间开销也越小。

因此，小 P 用两者差的绝对值 |g(x)−f(x)|来表示处理询问 xx 时的误差。

为了整体评估小 P 同学提出的方法在序列 A 上的表现，试计算：

error(A)=∑i=0N−1|g(i)−f(i)|=|g(0)−f(0)|+⋯+|g(N−1)−f(N−1)|

输入格式

输入的第一行包含空格分隔的两个正整数 n 和 N。

输入的第二行包含 n 个用空格分隔的整数 A1,A2,⋯,An。

注意 A0 固定为 0，因此输入数据中不包括 A0。

输出格式

仅输出一个整数，表示 error(A)的值。

数据范围

70%70% 的测试数据满足 1≤n≤200且 n<N≤1000；
全部的测试数据满足 1≤n≤105 且 n<N≤109

输入样例1：

3 10
2 5 8

输出样例1：

5

样例1解释

A=[0,2,5,8]
r=⌊Nn+1⌋=⌊103+1⌋=2

i	0	1	2	3	4	5	6	7	8	9
f(i)	0	0	1	1	1	2	2	2	3	3
g(i)g(i)	0	0	1	1	2	2	3	3	4	4
∥g(i)−f(i)∥∥g(i)−f(i)∥	0	0	0	0	1	0	1	1	1	1

输入样例2：

9 10
1 2 3 4 5 6 7 8 9

输出样例2：

0

输入样例3：

2 10
1 3

输出样例3：

6

样例3解释

A=[0,1,3]
r=⌊Nn+1⌋=⌊102+1⌋=3

i	0	1	2	3	4	5	6	7	8	9
f(i)	0	1	1	2	2	2	2	2	2	2
g(i)	0	0	0	1	1	1	2	2	2	3
∥g(i)−f(i)∥	0	1	1	1	1	1	0	0	0	1

提示

需要注意，输入数据 [A1⋯An]并不一定均匀分布在 (0,N) 区间，因此总误差 error(A)可能很大。

题解：

#include <iostream>
#include <vector>
#include <cmath>using namespace std;int main() {int n, N;cin >> n >> N;int r = N / (n + 1); // 计算比例系数 rvector<int> A(n + 1); A[0] = 0; for (int i = 1; i <= n; i++) {cin >> A[i];}long long error = 0;for (int i = 0; i <= n; i++) { // 遍历每个区间int L = A[i]; // 当前区间的左端点int R = (i == n) ? N : A[i + 1]; // 当前区间的右端点，最后一个区间右端点为 Nint f_i = i; // f(i) 在该区间内恒为 iint g_L = L / r; // g(L) = ⌊L / r⌋，即 L 处的 g(i) 值int g_R = (R - 1) / r; // g(R-1) = ⌊(R-1) / r⌋，即 R-1 处的 g(i) 值if (g_L == g_R) { // 如果 g(i) 在整个区间[L, R)内保持不变error += abs(f_i - g_L) * (R - L); // 直接计算整个区间的误差} else { // 如果 g(i) 在区间内有变化for (int g_i = g_L; g_i <= g_R; g_i++) { // 遍历 g(i) 变化的不同区间int seg_L = max(L, g_i * r); // 计算当前 g(i) 段的左端点int seg_R = min(R, (g_i + 1) * r); // 计算当前 g(i) 段的右端点error += abs(f_i - g_i) * (seg_R - seg_L); // 计算该段误差并累加}}}cout << error;return 0;
}

总结：

• f(i) = i，因为 A[i] ≤ i < A[i+1] 时 f(i) 的值就是 j
• g(i) = ⌊i / r⌋，在 [L, R) 计算 g(L) 和 g(R-1)
• g_L 是 L 除以 r 的商，即区间开始时 g(i) 的值。
• g_R 是 (R - 1) 除以 r 的商，即区间结束时 g(i) 的值。

• 如果 g_L == g_R，表示在整个区间内，g(i) 是一个固定值（即 g(i) 不变化），此时我们直接计算整个区间内的误差：

  sum += (long long)abs(f_i - g_L) * (R - L);

  即，所有 i 值在这个区间内的误差都相同，直接乘上区间的长度 (R - L)。

分段计算误差（当 g(i) 变化时）

如果 g(i) 在该区间内发生变化（即 g_L != g_R），我们需要将区间 [L, R) 分成多个子区间，每个子区间内 g(i) 是一个常数。这样可以分别计算每个子区间的误差

为什么使用 g_i * r 和 (g_i + 1) * r 来计算左右端点

1. g(x) 的变化：

   • g(x) 是通过 ⌊ x / r ⌋ 来计算的，也就是说，如果 x 在 g(x) = k 时，那么 k * r <= x < (k + 1) * r。例如，如果 r = 3，那么：
     • 当 g(x) = 0 时，x 必须在 [0, 3) 区间。
     • 当 g(x) = 1 时，x 必须在 [3, 6) 区间。
     • 当 g(x) = 2 时，x 必须在 [6, 9) 区间。
     • 以此类推。

2. 当前区间的左右端点：

   • g(x) 值的变化会在 [g_i * r, (g_i + 1) * r) 这个区间之间发生。所以，对于每个 g(x) 值的区间，g(x) 是不变的，直到 x 达到下一个 g(x) 的分段边界。
   • g_i * r 就是当前 g(x) 值区间的左边界。
   • (g_i + 1) * r 就是下一个 g(x) 值区间的左边界。

3. 计算有效区间： 对于每个 g(x)，我们希望计算它在 [l, r) 区间中的误差。为了确保我们不超出这个区间，我们取 left 和 g_i * r 的较大值作为当前区间的左端点，取 right 和 (g_i + 1) * r 的较小值作为当前区间的右端点：

   • seg_l = max(l, g_i * r)：确保我们从真实的 left 开始，且不小于当前分段的左端点 g_i * r。
   • seg_r = min(r, (g_i + 1) * r)：确保我们在真实的 right 结束，且不超过当前分段的右端点 (g_i + 1) * r。

这样，seg_L 和 seg_R 就代表了当前 g(x) 值在区间 [L, R) 中的有效部分。

举个例子

假设：

• n = 3，N = 10
• r = 2
• A = [0, 2, 5, 8]

我们想计算误差 error(A)，需要对 f(i) 和 g(i) 进行比较。考虑对于 i 的某个范围，我们如何根据 g(i) 来划分。

计算过程：

1. 对于 i = 0 到 2，g(i) = ⌊ i / 3 ⌋，所以 g(i) 都是 0。

   • 这里的有效区间就是 [0, 3)，所以 g(i) 在这个区间内为 0。

2. 对于 i = 3 到 5，g(i) = ⌊ i / 3 ⌋ = 1。

   • 这里的有效区间是 [3, 6)，所以 g(i) 在这个区间内为 1。

3. 对于 i = 6 到 8，g(i) = ⌊ i / 3 ⌋ = 2。

   • 这里的有效区间是 [6, 9)，所以 g(i) 在这个区间内为 2。

4. 对于 i = 9，g(i) = ⌊ i / 3 ⌋ = 3。

在代码中：

对于每个区间 [L, R)，我们计算：

• g_L = L / r
• g_R = (R - 1) / r

然后将这个区间进一步拆分为 [g_i * r, (g_i + 1) * r)，并根据 max 和 min 保证没有超出原始的 [L, R) 区间。

总结

g_i * r 和 (g_i + 1) * r 代表了 g(x) 值变化的边界。在每个区间内，我们通过这些边界来确保只在有效区间内计算误差。

 

 

第一轮：i = 0 (区间 [0, 2))

• L = a[0] = 0, R = a[1] = 2。
• 计算：
  • f_i = 0，因为 A[0] ≤ x < A[1] 时，f(x) 为 0。
  • g_L = L / r = 0 / 2 = 0。
  • g_R = (R - 1) / r = (2 - 1) / 2 = 0。
• 由于 g_L == g_R，在该区间内 g(i) 始终为 0。

  sum += (long long)abs(f_i - g_L) * (R - L) = abs(0 - 0) * (2 - 0) = 0

• 误差为 0。

第二轮：j = 1 (区间 [2, 5))

• left = a[1] = 2, right = a[2] = 5。
• 计算：
  • f_i = 1，因为 A[1] ≤ x < A[2] 时，f(x) 为 1。
  • g_left = left / r = 2 / 2 = 1。
  • g_right = (right - 1) / r = (5 - 1) / 2 = 2。
• 由于 g_left != g_right，g(i) 在 [2, 5) 区间内发生变化。
  • 对于 g(i) 可能的值 1 和 2，计算每段的误差。
  • 对于 g_i = 1:

    segment_left = max(2, 1 * 2) = 2 segment_right = min(5, (1 + 1) * 2) = 4 sum += abs(f_i - g_i) * (segment_right - segment_left) = abs(1 - 1) * (4 - 2) = 0

  • 对于 g_i = 2:

    segment_left = max(2, 2 * 2) = 4 segment_right = min(5, (2 + 1) * 2) = 5 sum += abs(f_i - g_i) * (segment_right - segment_left) = abs(1 - 2) * (5 - 4) = 1

• 误差为 1。

 

第三轮：j = 2 (区间 [5, 8))

• left = a[2] = 5, right = a[3] = 8。
• 计算：
  • f_i = 2，因为 A[2] ≤ x < A[3] 时，f(x) 为 2。
  • g_left = left / r = 5 / 2 = 2。
  • g_right = (right - 1) / r = (8 - 1) / 2 = 3。
• 由于 g_left != g_right，g(i) 在 [5, 8) 区间内发生变化。
  • 对于 g(i) 可能的值 2 和 3，计算每段的误差。
  • 对于 g_i = 2:

    cpp

    复制编辑

    segment_left = max(5, 2 * 2) = 5 segment_right = min(8, (2 + 1) * 2) = 6 sum += abs(f_i - g_i) * (segment_right - segment_left) = abs(2 - 2) * (6 - 5) = 0

  • 对于 g_i = 3:

    segment_left = max(5, 3 * 2) = 6 segment_right = min(8, (3 + 1) * 2) = 8 sum += abs(f_i - g_i) * (segment_right - segment_left) = abs(2 - 3) * (8 - 6) = 2

• 误差为 2。

 

 

第四轮：j = 3 (区间 [8, 10))

• left = a[3] = 8, right = N = 10。
• 计算：
  • f_i = 3，因为 A[3] ≤ x < N 时，f(x) 为 3。
  • g_left = left / r = 8 / 2 = 4。
  • g_right = (right - 1) / r = (10 - 1) / 2 = 4。
• 由于 g_left == g_right，在该区间内 g(i) 始终为 4。

  sum += (long long)abs(f_i - g_left) * (right - left) = abs(3 - 4) * (10 - 8) = 2

• 误差为 2。

 

• 分段计算误差：代码的目标是计算每个整数 i 在区间 [a[j], a[j+1]) 内的误差。为了高效计算误差，利用了 g(i) 是按比例递增的这一特点。即 g(i) 会在区间内的某些值变动，在某些情况下，它是连续的。所以，代码通过分段的方式来处理这些变化。

• 区间内的线性变化：对于区间 [a[j], a[j+1])，f(i) 直接等于 j，而 g(i) 是根据 i 除以比例系数 r 计算出来的。g(i) 在该区间内是分段的，即在某些 i 值下，g(i) 是固定的，而在其他值下，它会变化。