题解：CF2094G Chimpanzini Bananini

枫原万叶 · 2025-04-25 20:35:38 · 题解

CF2094G Chimpanzini Bananini 题解

分析

体面大概意思是操作一个空数组，可以进行一下三种操作：

1. 最后一个元素移到最前面。
2. 数组元素顺序翻转。
3. 在数组末尾添加一个元素。

每次操作后输出所有元素乘以其下标的和，这个操作次数最多 2 \times 10^5 次。

那么我们来看一下每一个操作应该怎么做：

• 操作一：直接计算新元素的数值，即 k \times (当前长度 + 1) 。
• 操作二：反转后，原位置 i 变为 n + 1 - i 。总和变为 suma \times (n + 1) - sum ，其中这里的 suma 是元素总和。
• 操作三：将最后一个元素移到最前面，其他元素右移。总和变化就是 sum = sum + suma - x \times n （这里的 x 是被移动的元素的值）。

这里我们转换一个思路，对于反转我们其实不需要整个数组反转，而是调整操作一和操作三的添加或者移动位置就可以了。

这里进行了一个数学转换和标记，直接把每次操作的时间复杂度简化至 O(1) 。

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int q;
        scanf("%d", &q);
        deque<int> dq;
        int rev = 0;
        ll sum = 0, suma = 0;
        int n = 0;
        while (q--) {
            int s;
            scanf("%d", &s);
            if (s == 3) {
                int k;
                scanf("%d", &k);
                if (rev) {
                    dq.push_front(k);
                } else {
                    dq.push_back(k);
                }
                sum += k * (n + 1LL);
                suma += k;
                n++;
            } else if (s == 1) {
                int l;
                if (rev) {
                    l = dq.front();
                } else {
                    l = dq.back();
                }
                sum += suma - l * (ll)n;
                if (rev) {
                    dq.push_back(dq.front());
                    dq.pop_front();
                } else {
                    dq.push_front(dq.back());
                    dq.pop_back();
                }
            } else if (s == 2) {
                rev ^= 1;
                sum = (n + 1LL) * suma - sum;
            }
            printf("%lld\n", sum);
        }
    }
    return 0;
}