F. Firefly's Queries - 题解

比赛与标签

比赛: Codeforces Round 971 (Div. 4) 标签: bitmasks, data structures, flows, math 难度: *1700

题目大意喵~

主人你好呀~！这道题是关于一个叫做 Firefly 的小可爱和她神奇的数组变换的喵~

事情是这样的：

首先，我们有一个长度为 n 的数组 a。
然后，我们要生成 n 个 a 的循环移位版本。第 i 个循环移位 c_i 就是把 a 的前 i-1 个元素挪到末尾去。
接着，把这 n 个循环移位后的数组 c_1, c_2, ..., c_n 按顺序拼接起来，形成一个超级长~的数组 b。这个 b 的长度会是 n * n 哦！
最后，会有 q 次询问。每次询问会给出一个区间 [l, r]，我们需要计算出 b 数组在这个区间里的所有元素的和是多少。

因为 n 可以很大，所以 b 数组的长度最大能到 (2*10^5)^2，也就是 4 * 10^{10}！直接把 b 数组造出来是绝对不行的说，会把内存和时间都撑爆的喵！所以，我们必须找到一个更聪明的办法呐。

解题思路分析呐

面对这么大的一个数组，我们肯定不能硬来，要巧取才行！解决区间求和问题，我们的老朋友前缀和就要登场啦~

如果我们能快速算出一个函数 F(x)，它表示 b 数组前 x 个元素的和，那么对于任何查询 [l, r]，答案就是 F(r) - F(l-1)，对吧？

那么，关键问题就变成了：如何高效地计算 F(x) 呢？

让我们来仔细看看 b 数组的结构。b 是由 n 个长度为 n 的数组块（c_1, c_2, ...）拼接而成的。

要求前 x 个元素的和，我们可以把这 x 个元素分成两部分：

若干个完整的数组块
最后一个不完整的数组块（的开头部分）

举个例子，假设我们要计算 F(x)：

x 里面包含了多少个完整的长度为 n 的块呢？这个数量是 k = (x-1) / n。（这里用 x-1 是因为编程里用0-based索引更方便，而题目是1-based的，喵~）
剩下的部分有多少个元素呢？这个数量是 rem+1，其中 rem = (x-1) % n。这些元素来自第 k+1 个循环移位块 c_{k+1}。

第一部分：完整块的和

每个循环移位 c_i 只是原数组 a 的元素换了换位置，所以它们的元素总和都等于 a 的总和。我们先把 a 的总和算出来，记作 total_sum。 k 个完整块的总和就是 k * total_sum。很简单对吧！

第二部分：不完整块的和

这部分稍微有点绕，但别怕，有本猫娘在呢！我们需要计算第 k+1 个循环移位块 c_{k+1} 的前 rem+1 个元素的和。

c_{k+1} 是从原数组 a 的第 k 个元素（0-based索引）开始的循环移位。也就是说，c_{k+1} 的开头是 a_k, a_{k+1}, ..., a_{n-1}, a_0, ...。我们需要求和的，就是 a_k, a_{k+1}, ..., a_{k+rem} 这一段（所有下标都要对 n 取模）。

处理循环数组的求和问题，有一个超级好用的技巧：数组翻倍！我们创建一个新数组 A，它等于 a 和 a 自己拼接起来，A = a + a。A 的长度是 2n。这样一来，原来在 a 上的任何一个长度不超过 n 的循环连续子段，都变成了 A 上的一个普通的连续子段。比如，a_k, ..., a_{k+rem} 这一段，就正好是 A 数组里从下标 k 到 k+rem 的那一段！

为了快速求 A 上任意区间的和，我们可以再对 A 预处理一个前缀和数组 P。 P[i] 表示 A 数组前 i 个元素的和。那么，A[k...k+rem] 的和就是 P[k+rem+1] - P[k] 啦！

整合起来！ 我们的 F(x) 函数的计算公式就出来啦 (使用0-based索引 x' = x-1): k = x' / nrem = x' % nF(x) = k * total_sum + (P[k+rem+1] - P[k])

这样，每次查询我们只需要做几次算术运算和查表，时间复杂度就是 O(1) 的说！

最终步骤总结喵~

读入 n 和 q。
读入数组 a，并计算出它的总和 total_sum。
创建一个长度为 2n 的数组 A，内容是 a 拼接 a。
计算 A 的前缀和数组 P。
对于每个查询 [l, r]，计算 F(r) - F(l-1) 作为答案。记得要用 long long 来存结果哦，不然会溢出的！

代码实现喵~

cpp

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll; // 使用 long long 防止求和时溢出喵

int main() {
    // 加速输入输出，让程序跑得更快一点！
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        ll n, q;
        cin >> n >> q;
        vector<ll> a(n);
        ll total = 0; // 用来存储数组 a 的总和
        for (ll i = 0; i < n; i++) {
            cin >> a[i];
            total += a[i];
        }

        // 技巧一：数组翻倍，处理循环问题
        // 把 a 复制一份拼在后面，方便处理循环移位的区间和
        vector<ll> A(2 * n);
        for (ll i = 0; i < 2 * n; i++) {
            A[i] = a[i % n];
        }

        // 技巧二：预处理前缀和
        // P[i] 存储 A 数组前 i 个元素的和
        vector<ll> P(2 * n + 1, 0);
        for (ll i = 1; i <= 2 * n; i++) {
            P[i] = P[i - 1] + A[i - 1];
        }

        // 定义一个 lambda 函数 F(x) 来计算 b 数组前 x 个元素的和
        // 这是整个解法的核心所在！
        auto F = [&](ll x) -> ll {
            if (x == 0) {
                return 0; // 前0个元素的和当然是0啦
            }
            // 题目是1-based，我们转成0-based计算更方便
            x--; 
            
            // k 是完整的块数
            ll k = x / n;
            // rem 是最后一个不完整块的最后一个元素的下标
            ll rem = x % n;
            
            // F(x) = (k个完整块的和) + (不完整块的和)
            // k个完整块的和 = k * total
            // 不完整块是 c_{k+1} 的前 rem+1 个元素，其和等于 A[k...k+rem] 的和
            // A[k...k+rem] 的和 = P[k+rem+1] - P[k]
            return k * total + (P[k + rem + 1] - P[k]);
        };

        // 处理 q 次查询
        while (q--) {
            ll l, r;
            cin >> l >> r;
            // 区间 [l, r] 的和 = 前 r 个元素的和 - 前 l-1 个元素的和
            cout << F(r) - F(l - 1) << '\n';
        }
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(n + q) 的说。对于每个测试用例，我们需要 O(n) 的时间来读取输入、构建翻倍数组 A 和计算前缀和数组 P。这部分是预处理。之后，每次查询都调用 F 函数，这个函数内部只有几次数学运算和数组访问，是 O(1) 的。所以 q 次查询总共需要 O(q) 的时间。总时间复杂度就是 O(n + q) 啦，非常高效！
空间复杂度: O(n) 的说。我们主要需要额外的空间来存储原数组 a (O(n))，翻倍数组 A (O(2n))，以及前缀和数组 P (O(2n))。总的来说，空间开销是和 n 成正比的，所以是 O(n) 的喵。

知识点与总结喵~

这道题真是一道非常好的思维训练题呢！它教会了我们如何处理那些看起来大到吓人的 "隐式" 数组。

核心的知识点和技巧总结一下：

前缀和思想: 这是解决静态区间和问题的万能钥匙！sum(l, r) = prefix(r) - prefix(l-1) 这个思想一定要牢牢记住呐。
转化与分解: 面对复杂问题，尝试把它分解成几个更简单的子问题。我们成功地把 b 数组的前缀和分解成了 "完整块" 和 "不完整块" 两部分。
循环数组的处理: "数组翻倍" 是一个非常优雅的技巧，能把循环的问题变成线性问题，大大简化了后续的计算。
数学建模: 将问题的结构抽象成数学公式 F(x) 是解题的关键一步。这需要我们有敏锐的观察力和清晰的逻辑。
注意数据范围: 看到求和问题和较大的 n，就要立刻想到 long long，这是一个好习惯的说！

希望这篇题解能帮助到你，让你也爱上这种用智慧解决难题的感觉！加油哦，你一定可以的！喵~ >ω<

F. Firefly's Queries - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路分析呐 ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵~ ​