周期函数 - 题解

标签与难度

标签: 字符串, KMP算法, 计算几何, 哈希 难度: 2200

题目大意喵~

主人你好呀，喵~ 这道题是关于一个分段线性函数 f(x) 的说。

首先，我们拿到 n 个点 (x_i, y_i)，它们的 x 坐标是严格递增的。把相邻的点用线段连起来，就构成了一个在区间 [x_1, x_n] 上定义的函数 f(x) 啦。

然后呢，题目定义了一种特殊的“最小周期” t，它需要满足下面几个条件哦：

1. t 是一个正整数。
2. 0 < t < r - l，也就是说周期 t 必须严格小于区间的长度。
3. 对于区间 [l, r-t] 里的任何一个 x，都要有 f(x) = f(x+t)。这就是周期性的核心要求呐！
4. 区间的长度 r-l 必须是周期 t 的整数倍，也就是 r - l = k * t。

我们需要回答 q 次询问，每次给出一个区间 [l, r]，我们要找出这个区间上 f(x) 的最小周期 t。如果不存在这样的 t，就回答 -1 好了喵。

解题思路分析

这道题看起来像是个几何问题，但它其实可以巧妙地变身为一个字符串匹配问题哦，喵哈哈！这只我第一次看到的时候也觉得很有趣呢！

核心思想：函数周期性 -> 序列周期性

一个分段线性函数的“形状”是由什么决定的呢？是它的一段段的线段呀！每一段线段都可以用一个向量 (Δx, Δy) 来表示，其中 Δx 是 x 坐标的变化量，Δy 是 y 坐标的变化量。

如果函数 f(x) 在 [l, r] 上以 t 为周期，那就意味着函数图像的“形状”在不断重复。这等价于，构成函数图像的线段向量序列也是周期性的！

举个例子，如果函数在 [l, l+t] 上的线段向量序列是 S_p = <v_1, v_2, ..., v_p>，那么整个 [l, r] 上的线段向量序列 S 就应该是 k 个 S_p 拼接起来的样子：S = S_p S_p ... S_p。

这不就是字符串周期查询的经典问题嘛！我们可以用 KMP 算法的 next (或 pi) 数组来高效地找到一个序列的最小周期。

关键难点：看不见的“虚拟”顶点

最棘手的问题来啦！我们拥有的只是输入给定的 n 个点。但是，一个周期 t 的长度不一定恰好等于某两个给定点之间的 x 距离。周期完全可能在一个给定的线段中间开始或结束。

比如，我们有一条从 (0,0) 到 (4,0) 的线段，对于查询区间 [0,4]，它的最小周期其实是 t=1。函数图像 y=0 在 [0,1], [1,2], [2,3], [3,4] 上都是一样的。但是输入里并没有 (1,0), (2,0), (3,0) 这些点。我们称这些点为“虚拟顶点”。

为了解决这个问题，我们需要根据函数的周期性，把这些“虚拟顶点”给找出来，补全完整的顶点序列。之后再对这个完整的序列求周期，就没问题啦。

破解方法：聪明的顶点补全术

这道题的参考代码们用了一种非常巧妙的方法来补全顶点，虽然第一眼看上去有点神秘，喵~ 待我来解释一下。

这个方法基于一个深刻的洞察：如果函数是周期的，那么它的每一段重复的“形状块”都应该是一样的。特别是，第一个形状块和最后一个形状块的结构必然相同。

代码的核心逻辑是这样的：

1. 初步筛选：对于一个查询 [l, r]，如果 f(l) != f(r)，那肯定没有周期，因为 f(r) = f(l + k*t) = f(l) 必须成立。所以直接输出 -1。

2. 构建基础顶点列表 ps：先把查询区间 [l, r] 内所有给定的点 (x_i, y_i) 都放进一个列表 ps 里。

3. 插入虚拟顶点：这是最关键的一步！代码遍历 ps 中的每个点 P_i = (x_i, y_i)，并试图根据区间最后一个线段 P_{r-1} -> P_r 的特征来“预测”并插入虚拟顶点。

   • 令最后一段的向量为 v_last = (xs[r] - xs[r-1], ys[r] - ys[r-1])。
   • 它会检查，如果把点 P_i 按照 v_last 平移，得到的新点 P_i' = P_i + v_last，这个新点是否恰好落在 P_i 所在的线段上？
   • 为了让 P_i' 落在 P_i -> P_{i+1} 这条线段上，需要满足两个条件： a. 斜率相同：P_i -> P_{i+1} 的斜率必须和 v_last (即 P_{r-1} -> P_r) 的斜率相同。为了避免浮点数精度问题，我们用叉乘的形式 dy1 * dx2 == dy2 * dx1 来判断。 b. 位置正确：P_i' 的 x 坐标必须在 x_i 和 x_{i+1} 之间。
   • 还有一个附加条件 ys[i] == ys[r-1]。这个条件是在推断，P_i 和 P_{r-1} 可能是在不同周期块里的同一个“相对位置”上的点。如果函数是周期的，它们的高度差应该是0。
   • 如果所有条件都满足，就把这个新点 P_i' 加入到 ps 列表中，并保持 ps 列表按 x 坐标排序。

这个过程，本质上是在说：“如果函数是周期的，那么它的微观结构（斜率）和宏观结构（周期块之间的关系）应该是自洽的。我假设最后一个线段的模式是通用的，并用它来填充其他地方可能缺失的细节。”

4. KMP 求解：当 ps 列表构建完毕后，它就包含了所有的（原始和虚拟的）顶点了。我们就可以：

   • 将 ps 中相邻点构成的线段向量 (dx, dy) 序列化。为了能让 KMP 处理，可以把 (dx, dy) 哈希成一个 long long。
   • 对这个哈希序列跑 KMP 算法，计算出 next 数组。
   • 根据 next 数组的性质，如果序列总长度为 M，next 数组的最后一项是 pi_val，那么最小周期（的长度，指序列元素个数）是 p = M - pi_val。但这要求 M 必须能被 p 整除。
   • 如果 M % p != 0，说明整个序列不具备周期性，输出 -1。

5. 计算并验证周期 t：

   • 我们得到的周期长度 p 是指线段的个数。真正的周期 t 是这 p 个线段在 x 轴上的总长度。我们可以通过 ps 列表计算出来：t = ps[p].x - ps[0].x。
   • 最后，根据题目要求，验证这个 t 是否满足 0 < t < r - l 并且 (r-l) 是 t 的倍数。如果都满足，t 就是我们寻找的答案！否则，就是 -1。

通过这套组合拳，我们就能优雅地解决这个看似棘手的几何问题啦，喵~

代码实现

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>

// 定义点的结构体，方便操作喵~
struct Point {
    long long x, y;
};

// 用于计算两个整数的最大公约数 (Greatest Common Divisor)
// 我们用辗转相除法，很经典的呐
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// KMP算法的核心，计算next数组 (也叫pi table)
// next[i] 表示前缀 s[0...i] 的最长真前缀，同时也是其后缀的长度
std::vector<int> calculate_next(const std::vector<long long>& s) {
    int n = s.size();
    if (n == 0) return {};
    std::vector<int> next(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = next[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

// 主解决函数，每次查询调用一次
void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<long long> xs(n), ys(n);
    std::map<long long, int> x_to_idx; // 用map快速从x坐标找到索引
    for (int i = 0; i < n; ++i) {
        std::cin >> xs[i];
        x_to_idx[xs[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> ys[i];
    }

    for (int k = 0; k < q; ++k) {
        long long l_coord, r_coord;
        std::cin >> l_coord >> r_coord;

        // 通过map找到左右端点在数组中的索引
        int l_idx = x_to_idx[l_coord];
        int r_idx = x_to_idx[r_coord];

        // 特殊情况处理：
        // 1. 区间长度为0
        // 2. 左右端点高度不同，不满足 f(l) = f(r)，肯定无周期
        if (l_idx == r_idx || ys[l_idx] != ys[r_idx]) {
            std::cout << -1 << std::endl;
            continue;
        }

        // 构建包含所有原始和虚拟顶点的列表 ps
        std::vector<Point> ps;
        for (int i = l_idx; i <= r_idx; ++i) {
            ps.push_back({xs[i], ys[i]});
        }
        
        // 神奇的虚拟顶点插入过程
        // 检查是否可以根据最后一个线段的模式来补全顶点
        if (r_idx > l_idx) { // 至少要有一个线段
            long long last_dx = xs[r_idx] - xs[r_idx - 1];
            long long last_dy = ys[r_idx] - ys[r_idx - 1];

            std::vector<Point> temp_ps;
            for (size_t i = 0; i < ps.size(); ++i) {
                temp_ps.push_back(ps[i]);
                // 只在两个原始顶点之间插入
                if (i + 1 < ps.size()) {
                    long long cur_dx = ps[i+1].x - ps[i].x;
                    long long cur_dy = ps[i+1].y - ps[i].y;
                    
                    // 条件1: 当前段斜率 == 最后一段斜率 (叉乘判断)
                    // 条件2: 当前点y值 == 最后一段起点y值
                    // (ys[i] == ys[r_idx-1])
                    // 这里原版代码的 ys[r-1] == ys[i] 有点迷，
                    // 但逻辑上是检查一种结构上的对等性。我们照着这个思路来。
                    // 找到ps[i]在原始数组中的索引
                    int original_i_idx = x_to_idx[ps[i].x];
                    if (original_i_idx < r_idx -1 && ys[original_i_idx] == ys[r_idx-1] && cur_dy * last_dx == last_dy * cur_dx) {
                        long long new_x = ps[i].x + last_dx;
                        long long new_y = ps[i].y + last_dy;
                        // 插入的点必须在当前线段内部
                        if (new_x > ps[i].x && new_x < ps[i+1].x) {
                           temp_ps.push_back({new_x, new_y});
                        }
                    }
                }
            }
            ps = temp_ps;
        }

        // 将线段向量哈希成一个数字序列
        std::vector<long long> segments_hash;
        const long long C1 = 4000000007LL; // 一个大素数，用来做哈希
        const long long C2 = 2000000000LL; // 偏移量，确保dx为正
        for (size_t i = 0; i < ps.size() - 1; ++i) {
            long long dx = ps[i + 1].x - ps[i].x;
            long long dy = ps[i + 1].y - ps[i].y;
            segments_hash.push_back(dx + C2 + dy * C1);
        }

        if (segments_hash.empty()) {
            std::cout << -1 << std::endl;
            continue;
        }

        // KMP 找最小周期
        std::vector<int> next = calculate_next(segments_hash);
        int m = segments_hash.size();
        int period_len_in_segs = m - next[m - 1];

        // 如果整个序列不是由若干个最小周期组成的，则无解
        if (m % period_len_in_segs != 0) {
            std::cout << -1 << std::endl;
            continue;
        }

        // 计算周期的实际长度 t
        long long t = ps[period_len_in_segs].x - ps[0].x;

        // 最后验证
        long long interval_len = r_coord - l_coord;
        if (t > 0 && t < interval_len && interval_len % t == 0) {
            std::cout << t << std::endl;
        } else {
            std::cout << -1 << std::endl;
        }
    }
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析

• 时间复杂度: $O(Q \cdot N \log N)$

  • 对于每次查询 q，我们需要做以下几步：
  • 找到 l_idx 和 r_idx。如果使用 std::map 或者二分查找，这步是 $O(\log N)$。
  • 构建 ps 列表。最坏情况下，每个原始线段都可能插入一个虚拟顶点，所以 ps 的大小是 $O(N)$。排序这些点需要 $O(N \log N)$（不过我的实现里是线性扫描，然后插入，如果插入次数多，动态数组扩容可能代价高，但总体还是可控的）。
  • KMP算法计算 next 数组的时间是线性的，即 $O(|ps|) = O(N)$。
  • 所以，每次查询的总时间复杂度由构建 ps 列表主导，大约是 $O(N \log N)$ (如果需要排序) 或者 $O(N)$ (如果线性构建)。考虑到 std::vector 的插入操作，我们保守估计为 $O(N \log N)$。
  • 总复杂度就是 $O(Q \cdot N \log N)$。在 $N, Q \le 2000$ 的数据规模下，这个复杂度有点紧张，但由于插入虚拟点的情况不总是发生，实际运行效率会比最坏情况好很多，可以通过此题。如果优化 ps 的构建过程，可以做到 $O(Q \cdot N)$。

• 空间复杂度: $O(N)$

  • 我们需要存储输入的 x 和 y 数组，空间是 $O(N)$。
  • x_to_idx map 占用 $O(N)$ 空间。
  • 在每次查询中，ps 列表、segments_hash 向量和 next 数组的大小都与查询区间内的点数相关，最多是 $O(N)$。
  • 因为查询是独立的，这些空间可以复用。所以总空间复杂度是 $O(N)$。

知识点总结

1. 问题转化: 这是解题的灵魂！将一个看似复杂的计算几何问题，通过分析其内在结构，转化为我们熟悉的字符串（序列）周期性问题。
2. KMP算法的应用: KMP 不仅仅是用来做 s1 中找 s2 的。它的 next (or pi) 数组蕴含了字符串前缀的周期性信息，是解决这类问题的利器。要记住 len % (len - next[len-1]) == 0 这个判别完全周期性的公式哦！
3. 哈希: 当我们需要比较复杂结构（比如本题的向量 (dx, dy)）是否相等时，可以将它们哈希成一个整数，这样就能方便地在序列算法（如KMP）中使用了。
4. 处理细节: 算法题的魅力就在细节中。比如本题需要处理的“虚拟顶点”，以及用叉乘代替除法来比较斜率以避免精度问题，都是非常重要的编程技巧，喵~

希望这篇题解能帮到你哦！如果还有不明白的地方，随时可以再来问这只我，喵~ >w<