跳转至

202112-2 序列查询新解

与上一题的比较

  1. 上一题是求和，而本题要求求绝对值的和，无法转化为两者求差的形式。
  2. \(f(x),g(x)\) 的变化是各自独立的，当 \(f(x)\) 改变时，\(g(x)\) 可能不变，也可能改变；\(g(x)\) 对 \(f(x)\) 也是如此。
  3. 对于所有数据点，\(n\) 和 \(N\) 都增大了许多。如果复杂度涉及到 \(n\)，则最多预计为 \(\mathbf{O}(n\log n)\) 级别；如果涉及到 \(N\)，则必须是亚线性级别。

70% 数据——计算出每个 f(x),g(x) 的值

由于1,2条限制，我们无法直接对 \(f(x),g(x)\) 分别进行处理。但我们可以求出每个 \(f(x),g(x)\) 的值，再计算求和即可。

\(f(x)\) 的计算同第一问，任意方法皆可。单个 \(g(x)\) 的值可以直接 \(\mathbf{O}(1)\) 求得。

100% 数据——对 f(x),g(x) 都相同的区间进行求和处理

注：为了防止混淆，将题目中的 \(r\) 改为 \(ratio\)。

假设 \(f(x)\) 一共有 \(x\) 种取值，\(g(x)\) 一共有 \(y\) 种取值。 直接来看 \(f(x),g(x)\) 的组合一共有 \(xy\) 种， 但注意到 \(f(x),g(x)\) 都是单调不递减函数，所以真正的组合只有 \(x+y\) 种。

在第一题中已经说明 \(f(x)\) 的取值范围为 \([0,n]\)，在 \(\mathbf{O}(n)\) 级别。 考虑 \(g(x)\) 的取值情况，将 \(ratio\) 的公式带入可以得到 \(g(x)=\lfloor \frac{x}{ratio}\rfloor=\lfloor\frac{x}{\lfloor \frac{N}{n+1}\rfloor}\rfloor\)。 由于 \(x\) 取值有 \(N\) 种，所以 \(g(x)\) 的取值是 \(\mathbf{O}(\frac{N}{\frac{N}{n+1}})=\mathbf{O}(n)\) 级别的。 所以，整体复杂度为 \(\mathbf{O}(n+n)=\mathbf{O}(n)\)。

提示

有些时候，题目给出的某些量的值会比较特殊（如本题 \(ratio=\lfloor\frac{N}{n+1}\rfloor\)）， 代表着出题人可能想要隐藏某些做法，但不得不为了让时间复杂度正确而妥协。 在没有思路的时候，可以作为突破口。

考虑范围问题：假设当前左端点为 \(l\)，如何找到右端点 \(r\)，满足 \(f(l)=f(l+1)=\cdots=f(r),g(l)=g(l+1)\cdots=g(r)\) 且 \(f(l)\not=f(r+1)\ or\ g(l)\not=g(r+1)\)。 我们可以对 \(f(x),g(x)\) 分别考虑:

  1. 对于 \(f(x)\) 而言，第一个满足 \(f(x)=f(l)+1\) 的 \(x\) 值为 \(A_{f_l + 1}\)。
  2. 对于 \(g(x)\) 而言，因为分母 \(ratio\) 是固定的，所以值相同的区间长度也是固定为 \(ratio\)。 我们不妨将 \(g(x)\) 值相同的数字为一组，则可以得到 \([0,ratio-1],[ratio,2\cdot ratio-1],\cdots,[n\cdot ratio,(n+1)\cdot ratio-1],\cdots\) 这样的分组序列，每组的 \(g(x)\) 取值为 \(0,1,\cdots,n,\cdots\)。 可以发现，对于一个数 \(l\)，其所属的分组是 \(\lfloor \frac{l}{ratio}\rfloor\)，也即 \(g(l)\)； 而下一组开始的第一个数为 \(ratio\cdot (g(l)+1)\)，从而可以得到右端点 \(r = ratio\cdot (g(l)+1) - 1\)。
  3. 在 \(f(x),g(x)\) 计算得到的右端点中，选择较小的一个作为计算的右端点。

计算完一段后，设 \(l=r+1\) 继续计算下一段，直到结束。时间复杂度 \(\mathbf{O}(n)\)。

代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define ll long long
const int maxn = 100010;
int n, N;
int a[maxn];
int rat, f, g;
ll ans = 0;
int main() {
    scanf("%d%d", &n, &N);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    rat = N / (n + 1); // 为了防止冲突，题目中 r 改为 rat
    int cur = 0;       // 用来计算 f(x)
    bool flag = false; // 如果需要更新 f(x) 值，则 flag = true
    for (int l = 0, r; l < N; l = r + 1) {
        flag = false;
        // 利用 f(x) 的值确定 r 的范围
        if (cur < n)
            r = a[cur + 1] - 1;
        else
            r = N - 1;
        // 判断 f(x), g(x) 谁先变化，选择较小的区间
        if ((l / rat + 1) * rat - 1 < r) {
            // 如果 g(x) 先变化，则改为选择 g(x)
            r = (l / rat + 1) * rat - 1;
        } else {
            // 如果 f(x) 先变化，则确定选择 f(x)，计算后更新 f(x)
            flag = true;
        }
        // [l, r] 区间内的值是相等的，可以求和
        ans += 1ll * (r - l + 1) * abs(l / rat - cur);
        // 更新 f(x) 的值
        if (flag)
            ++cur;
    }
    printf("%lld\n", ans);
    return 0;
}

评论