[数据结构与算法]CCF CSP202112-2 序列查询新解

CCF CSP202112-2 序列查询新解

题目背景

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

$A=[A_0,A_1,A_2,?,A_n]$ 是一个由 $n+1$ 个 $[0,N)$ 范围内整数组成的序列，满足 $0=A_0<A_1<A_2<?<A_n<N$。基于序列 $A$，对于 $[0,N)$ 范围内任意的整数 $x$，查询 $f(x)$ 定义为：序列 $A$ 中小于等于 $x$ 的整数里最大的数的下标。

对于给定的序列 $A$ 和整数 $x$，查询 $f(x)$ 是一个很经典的问题，可以使用二分搜索在 $O(log?n)$ 的时间复杂度内轻松解决。但在 IT 部门讨论如何实现这一功能时，小 P 同学提出了些新的想法。

题目描述

小 P 同学认为，如果事先知道了序列 A 中整数的分布情况，就能直接估计出其中小于等于 $x$ 的最大整数的大致位置。接着从这一估计位置开始线性查找，锁定 $f(x)$ 。如果估计得足够准确，线性查找的时间开销可能比二分查找算法更小。

比如说，如果 $A_1,A_2,?,A_n$ 均匀分布在 $(0,N)$ 的区间，那么就可以估算出：
$f(x)\approx \frac{(n+1)?x}{N}$

为了方便计算，小 P 首先定义了比例系数 $r=?\frac{N}{n+1}?$，其中 ? ? 表示下取整，即 r 等于 N 除以 $n+1$ 的商。进一步地，小 P 用 $g(x)=?\frac{x}{r}?$ 表示自己估算出的 $f(x)$ 的大小，这里同样使用了下取整来保证 $g(x)$ 是一个整数。

显然，对于任意的询问 $x\in [0,N)$，$g(x)$ 和 $f(x)$ 越接近则说明小 P 的估计越准确，后续进行线性查找的时间开销也越小。因此，小 P 用两者差的绝对值 $|g(x)?f(x)|$ 来表示处理询问 $x$ 时的误差。

为了整体评估小 P 同学提出的方法在序列 A 上的表现，试计算：
$error(A)={\sum }_{i=0}^{N?1}|g(i)?f(i)|=|g(0)?f(0)|+?+|g(N?1)?f(N?1)|$

输入格式

从标准输入读入数据。

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

输入的第二行包含 $n$ 个用空格分隔的整数 $A_1,A_2,?,A_n$。

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

输出格式

输出到标准输出。

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

样例1输入

3 10
2 5 8

样例1输出

5

样例1解释

$A=[0,2,5,8]$

$r=?\frac{N}{n+1}?=?\frac{10}{3+1}?=2$

样例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=?\frac{N}{n+1}?=?\frac{10}{2+1}?=3$

子任务

70% 的测试数据满足 $1\le n\le 200$ 且 $n<N\le 1000$；

全部的测试数据满足 $1\le n\le 10^5$ 且 $n<N\le 10^9$。

提示

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

要点分析

• 这题的思路其实是从上一题序列查询得来的，利用差分的思想，找到从 $A[i?1]$ 到 $A[i]$ 这一段中 $error(A)$ 的增加量是多少
• 其中，在 $A[i?1]$ 到 $A[i]$ 这一段中 $f(i)$ 的值都为 $n?1$ ，我们只需要计算这一段中 $g(i)$ 的取了哪些值，这些值分别出现了多少次
• 然后，由于要计算绝对值，我们需要分情况讨论：
  • $i?1\le g(i?1)$，这种情况下，绝对值之和等于$g()$ 之和（具体见代码，本质为等差数列加上最后一部分，减去最前面的一部分）减去 $f()$ 之和（n-1乘以数量）
  • $i?1\ge g(i)$，这种情况下，绝对值之和等于 $f()$ 之和减去 $g()$ 之和
  • $g(i?1)\le i?1\le g(i)$，这种情况下需要找到 $i?1$ 在 $g()$ 这个序列中的位置，然后分别计算小于 $i?1$ 和大于 $i?1$ 的部分
• 最后别忘了加上最后一段 $A[n]$ 到 $N?1$ 的部分

具体代码

#include <iostream>
using namespace std;
long long int n, N, r, ans = 0;
long long int pre = 0, cur = 0; // pre表示A[i-1],cur表示A[i]
long long int pre_x = 0, pre_y = 0; // pre_x表示g(i-1),pre_y表示g(i-1)的值在g()这个序列中是第几次出现的(从0开始计算)
long long int cur_x = 0, cur_y = 1; // cur_x表示g(i),cur_y表示g(i)的值在g()这个序列中是第几次出现的(从0开始计算)
int main()
{
    cin >> n >> N;
    r = N / (n + 1);
    for (long long int i = 1; i <= n + 1; i++)
    {
        if (i < n + 1)
            cin >> cur;
        else
            cur = N;
        cur_x = cur / r;
        cur_y = cur % r;
        long long int sum_theta_i = (pre_x - 1 + cur_x) * (cur_x - pre_x) * r / 2 - pre_y * pre_x + cur_y * cur_x; // 计算从A[i-1]到A[i](包括A[i-1],不包括A[i])这一段中g()的和
        if (i - 1 <= pre_x)
        {
            ans += sum_theta_i - (i - 1) * (cur - pre);
        }
        else if (i - 1 >= cur_x)
        {
            ans += (i - 1) * (cur - pre) - sum_theta_i;
        }
        else
        {
            long long int sum_low = (i - 1 - pre_x) * (pre_x + i - 2) * r / 2 - pre_y * pre_x; // 计算从A[i-1]到A[i](包括A[i-1],不包括A[i])这一段中小于i-1的部分的和
            long long int num_low = (i - 1 - pre_x) * r - pre_y; // 计算这一段中g()小于i-1的个数
            long long int sum_high = (cur_x - i) * (i + cur_x - 1) * r / 2 + cur_y * cur_x; // 计算从A[i-1]到A[i](包括A[i-1],不包括A[i])这一段中大于i-1的部分的和
            long long int num_high = (cur_x - i) * r + cur_y; // 计算这一段中g()大于i-1的个数
            ans += sum_high - sum_low + (i - 1) * (num_low - num_high);
        }
        pre = cur;
        pre_x = cur_x;
        pre_y = cur_y;
    }
    cout << ans;
}