G. Chimpanzini Bananini - 题解
比赛与标签
比赛: Codeforces Round 1017 (Div. 4) 标签: data structures, implementation, math 难度: *1700
小猫咪带你读题喵~
下午好呀，各位算法大师们！今天小猫娘要带大家攻略一道非常有趣的题目哦~ ฅ'ω'ฅ
这道题是关于一个叫 Chimpanzini Bananini 的大猩猩的（名字好长！）。他给了我们一个一开始空空如也的数组，然后我们可以对它进行三种操作：
- 循环右移 (Cyclic Shift): 数组
[a₁, a₂, ..., aₙ]会变成[aₙ, a₁, a₂, ..., aₙ₋₁]。就是把最后一个元素拿到最前面来啦。 - 翻转 (Reverse): 数组
[a₁, a₂, ..., aₙ]会变成[aₙ, aₙ₋₁, ..., a₁]。整个倒过来！ - 追加 (Append): 在数组末尾加上一个新元素
k。
我们的任务是，在每一次操作之后，都要计算并输出当前数组的 Rizziness 值。
那什么是 Rizziness 呢？它是一个带权重的和，计算公式是 b₁*1 + b₂*2 + ... + bₘ*m。也就是说，每个元素的值要乘以它所在的位置（从1开始数哦）。
因为操作次数 q 可能很大（最多 20 万次），我们必须找到一个超级高效的方法才行，不然就会超时啦！
喵喵的思考过程~
一看到这种要在每次操作后都输出一个值的题目，小猫娘的直觉就告诉我们，暴力模拟是肯定不行的说！你想呀，如果数组变得很长，每次都去循环一遍计算 Rizziness，或者去翻转整个数组，那时间复杂度就是 O(n) 的。q 次操作下来，总复杂度会变成 O(q²)，这可受不了呢！
所以，我们的目标是：让每次操作的复杂度都降到 O(1) 或者 O(log n)！
关键瓶颈与优化思路
瓶颈主要有两个：
- 数组操作：循环移位和翻转在普通数组（比如
std::vector）里都是O(n)的。 - Rizziness 计算：从头算一遍也是
O(n)的。
我们来一个一个解决！
解决数据结构瓶颈：双端队列 deque
我们需要一个能在数组两头都进行快速插入和删除的数据结构。这不就是为 std::deque（双端队列）量身定做的嘛！push_front, pop_front, push_back, pop_back 这些操作都是 O(1) 的，完美！
但是，deque 的 reverse 操作还是 O(n) 的。怎么办呢？这里有个超经典的技巧——懒人翻转法 (Lazy Reverse)！我们不用真的去翻转 deque，而是用一个布尔变量 reversed 来记录当前数组的逻辑状态。
- 如果
reversed是false，那deque的头部就是数组的逻辑头部。 - 如果
reversed是true，那deque的头部就代表数组的逻辑尾部！
这样，执行翻转操作就只需要 reversed = !reversed，瞬间完成，O(1) 搞定！
解决 Rizziness 计算瓶颈：数学推导大法！
接下来是重头戏！我们能不能在 O(1) 时间内更新 Rizziness 值呢？当然可以，用数学魔法！
我们设当前数组有 n 个元素，所有元素的和是 S，当前的 Rizziness 是 R。 R = a₁*1 + a₂*2 + ... + aₙ*nS = a₁ + a₂ + ... + aₙ
我们来分析三种操作对 R 的影响：
1. 追加元素 k (Append)
- 原数组：
[a₁, ..., aₙ] - 新数组：
[a₁, ..., aₙ, k]，长度变为n+1。 - 新的 Rizziness
R_new就是在旧的R的基础上，加上新元素k乘以它的新位置n+1。 R_new = (a₁*1 + ... + aₙ*n) + k*(n+1) = R_old + k*(n+1)- 这是一个
O(1)的更新！我们只需要维护好R，S和数组大小n就行啦。
2. 循环右移 (Cyclic Shift)
- 原数组：
[a₁, ..., aₙ]，Rizziness 为R_old。 - 新数组：
[aₙ, a₁, ..., aₙ₋₁]。 - 我们看看
R_new是什么：R_new = aₙ*1 + a₁*2 + a₂*3 + ... + aₙ₋₁*nR_new = aₙ*1 + (a₁*1+a₁) + (a₂*2+a₂) + ... + (aₙ₋₁*(n-1)+aₙ₋₁)把括号拆开，重新组合一下：R_new = aₙ*1 + (a₁*1 + a₂*2 + ... + aₙ₋₁*(n-1)) + (a₁ + a₂ + ... + aₙ₋₁)注意到(a₁*1 + ...)这部分就是R_old - aₙ*n，而(a₁ + ...)这部分就是S - aₙ。 代入进去：R_new = aₙ + (R_old - aₙ*n) + (S - aₙ) = R_old + S - aₙ*n - 又是一个
O(1)的更新！只需要知道R_old,S,aₙ和n。
3. 翻转 (Reverse)
- 原数组：
[a₁, a₂, ..., aₙ]，Rizziness 为R_old。 - 新数组：
[aₙ, aₙ₋₁, ..., a₁]。 R_new = aₙ*1 + aₙ₋₁*2 + ... + a₁*nR_new = Σ_{i=1 to n} a_{n+1-i} * i这里我们玩个小把戏，令j = n+1-i。当i从 1 变到n时，j就从n变到 1。所以i = n+1-j。R_new = Σ_{j=1 to n} a_j * (n+1-j)R_new = Σ (a_j * (n+1) - a_j * j)R_new = (n+1) * Σ a_j - Σ (a_j * j)R_new = (n+1) * S - R_old- 天哪，太神奇了！这又是一个
O(1)的更新公式！
整合思路
结合懒人翻转法和O(1)更新公式，我们的策略就清晰了：
- 用一个
std::deque<int> d存储数组元素。 - 用一个
bool reversed标记是否翻转。 - 用
long long current_rizz存储当前的 Rizziness。 - 用
long long sum_of_elements存储元素总和S。
每次操作：
- 追加
k：- 如果
!reversed，d.push_back(k)。 - 如果
reversed，追加到逻辑上的末尾，其实是deque的开头，所以d.push_front(k)。 - 更新
sum_of_elements += k。 - 更新
current_rizz += (long long)k * d.size()。（注意d.size()此时已经是新长度了）
- 如果
- 循环右移：
- 如果
!reversed，逻辑上的末尾是d.back()。取出它，按公式current_rizz += sum_of_elements - (long long)val * n更新，然后d.pop_back(),d.push_front(val)。 - 如果
reversed，逻辑上的末尾是d.front()。取出它，按同样公式更新，然后d.pop_front(),d.push_back(val)。
- 如果
- 翻转：
reversed = !reversed。- 按公式
current_rizz = (n + 1) * sum_of_elements - current_rizz更新。
这样，所有操作都可以在 O(1) 的时间内完成啦！是不是超级棒！
看这里看这里，代码实现喵~
#include <iostream>
#include <vector>
#include <deque>
#include <numeric>
#include <algorithm>
void solve() {
int q;
std::cin >> q;
// 用双端队列来模拟数组，喵~
std::deque<int> d;
// 懒人翻转标记，false代表正常顺序，true代表逻辑上是翻转的
bool reversed = false;
// 当前的Rizziness值
long long current_rizz = 0;
// 数组中所有元素的和
long long sum_of_elements = 0;
for (int i = 0; i < q; ++i) {
int type;
std::cin >> type;
if (type == 1) { // 循环右移
long long n = d.size();
if (n > 0) {
if (!reversed) {
// 正常顺序下，数组的最后一个元素在deque的尾部
int val = d.back();
// 应用我们的O(1)更新公式: R_new = R_old + S - val*n
current_rizz += sum_of_elements - (long long)val * n;
d.pop_back();
d.push_front(val);
} else {
// 翻转状态下，数组的最后一个元素在deque的头部
int val = d.front();
// 公式是一样的哦！
current_rizz += sum_of_elements - (long long)val * n;
d.pop_front();
d.push_back(val);
}
}
} else if (type == 2) { // 翻转
if (d.size() > 0) {
// 切换翻转状态
reversed = !reversed;
long long n = d.size();
// 应用我们的O(1)翻转公式: R_new = (n+1)*S - R_old
current_rizz = (n + 1) * sum_of_elements - current_rizz;
}
} else { // type == 3, 追加
int k;
std::cin >> k;
// 先更新总和
sum_of_elements += k;
if (!reversed) {
// 正常顺序，加到队尾
d.push_back(k);
} else {
// 翻转状态，逻辑上的队尾是deque的队头
d.push_front(k);
}
// 应用O(1)追加公式: R_new = R_old + k * new_size
current_rizz += (long long)k * d.size();
}
std::cout << current_rizz << "\n";
}
}
int main() {
// 加速输入输出，是个好习惯喵~
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}效率分析时间到!
- 时间复杂度: O(q) 的说。对于每一个查询，我们都只进行了常数次算术运算和
deque的O(1)操作。所以总的时间复杂度是线性的，超级快！ - 空间复杂度: O(q) 的说。在最坏的情况下，我们所有的操作都是追加元素，
deque中会存储q个元素。所以空间复杂度和操作次数成正比。
小猫娘的敲黑板时间!
这道题是不是超级有趣呀，喵~ 它完美地结合了数据结构、数学推导和一点点编程小技巧，让我们来总结一下学到了什么吧：
- 增量思想: 当需要频繁查询一个基于整个数据集计算的值时，不要每次都从头算！尝试寻找从旧状态到新状态的
O(1)或O(log n)递推关系。 std::deque的妙用: 它是处理序列两端增删问题的神器！要记住它哦。- 懒标记/状态标记: 像
reversed这样的布尔标记是避免昂贵O(n)操作（如真实翻转、删除）的常用高效技巧。 - 数学推导能力: 算法竞赛不仅仅是敲代码，更是思维的体操。花时间在纸上推导公式，往往能发现通往高效解法的捷径！
希望这篇题解能帮到你哦！如果遇到了困难，不要灰心，多思考一下，或者换个角度看看问题，你一定能找到突破口的！加油，未来的算法大师，喵~ (ฅ^•ﻌ•^ฅ)