Chimpanzini Bananini 的数组操作 详细题解

问题描述

我们有一个初始为空的数组。可以进行以下三种操作（操作是持久的，即每次操作都会修改数组并保留结果）：

1. 循环移位：将数组的最后一个元素移动到开头。
   形式化：$[a_1, a_2, \dots, a_n] \to [a_n, a_1, a_2, \dots, a_{n-1}]$。
2. 反转数组：将整个数组逆序。
   形式化：$[a_1, a_2, \dots, a_n] \to [a_n, a_{n-1}, \dots, a_1]$。
3. 追加元素：在数组末尾添加一个整数 $k$。
   形式化：$[a_1, a_2, \dots, a_n] \to [a_1, a_2, \dots, a_n, k]$。

每次操作后，需要计算数组的 rizziness，定义为：

$$\text{rizziness} = \sum_{i=1}^{n} a_i \cdot i = a_1 \cdot 1 + a_2 \cdot 2 + \dots + a_n \cdot n $$

其中 $n$ 是数组当前长度。

输入保证：每个测试用例的第一个操作一定是追加操作（类型 3）。

输入输出格式

输入
第一行一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例数。
每个测试用例第一行一个整数 $q$ ($1 \le q \le 2\cdot 10^5$)，表示操作总数。
接下来 $q$ 行，每行第一个整数 $s$ 表示操作类型：

• $s=1$：循环移位（无额外输入）
• $s=2$：反转数组（无额外输入）
• $s=3$：追加操作，后面跟一个整数 $k$ ($1 \le k \le 10^6$)

输出
对于每个操作，输出操作后数组的 rizziness。

核心观察与思路

需要维护什么？

如果每次操作后暴力计算 rizziness，复杂度 $O(nq)$ 会超时。我们需要 动态维护 当前分数。

设数组为 $a_1, a_2, \dots, a_n$，我们维护以下变量：

• n：数组长度
• tot：数组元素总和 $\sum a_i$
• norm：正向分数 $\sum_{i=1}^n a_i \cdot i$
• rev：反向分数，即将数组逆序后的分数 $\sum_{i=1}^n a_i \cdot (n+1-i)$

为什么需要 rev？

• 反转操作（类型 2）如果用真实翻转数组会很慢。但如果我们同时维护正向和反向的分数，反转操作就可以简单地交换 norm 和 rev。
• 同时，我们也维护两个双端队列：qNorm（正向顺序）和 qRev（反向顺序），反转时也交换它们。

恒等式

容易验证：

$$norm + rev = \sum a_i \cdot (i + n+1-i) = (n+1) \cdot tot $$

这个关系可以用来验证维护的正确性，但本题解中使用显式维护 rev 的方法，与标准程序一致。

选择的数据结构

因为循环移位需要从一端移除元素并添加到另一端，双端队列 std::deque 是最佳选择。

• qNorm 按正向存储：qNorm[0] = a_1，qNorm.back() = a_n
• qRev 按反向存储：qRev[0] = a_n，qRev.back() = a_1

两个队列同步维护，方便在反转操作时直接交换。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int norm = 0, rev = 0;
    int q; cin >> q;
    int tot = 0;
    int n = 0;
    deque<int> qNorm, qRev;
    int p = 0;
    while (q--) {
        int s; cin >> s;
        if (s == 1) {
            int last = qNorm.back();
            qNorm.pop_back();
            qNorm.push_front(last);
            norm += (tot - last);
            norm -= last * n;
            norm += last;

            last = qRev.front();
            qRev.pop_front();
            qRev.push_back(last);
            rev -= (tot - last);
            rev += last * n;
            rev -= last;
        }
        else if (s == 2) {
            swap(rev, norm);
            swap(qNorm, qRev);
        }
        else if (s == 3) {
            n++;
            int k; cin >> k;
            qNorm.push_back(k);
            qRev.push_front(k);
            norm += k * n;
            rev += tot;
            rev += k;
            tot += k;
        }
        cout << norm << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}