题解：CF2094G Chimpanzini Bananini

Tomwsc · 2025-04-29 13:27:32 · 题解

CF2094G Chimpanzini Bananini 题解

思路

考虑在 O(1) 的时间复杂度内完成每一次操作。同时，因为涉及翻转操作，所以考虑使用双端队列，因为该数据结构可以维护两边操作。此时，操作 2 便变成了换成双端队列的另外一端操作。

设此时数组的答案为 ans，数组的个数为 sz，数组中数的和为 num。

• 对于操作 1，容易得到 ans\leftarrow ans - \text{此时的最后一个元素}\times sz + num。然后把此时的最后一个元素放进此时的队首，再执行 pop 操作即可。
• 对于操作 2，我们发现每个元素的位置变成了 n - i +1，所以 ans=\sum_{i=1}^{sz}(n-i+1)\times a_i，对比原答案：ans=\sum_{i=1}^{sz}i\times a_i。可以发现 ans\leftarrow (sz+1)\times num-ans。
• 对于操作 3，只需把新的数 k 放进队列里，然后 num\leftarrow num+k，sz\leftarrow sz+1，ans\leftarrow ans+k\times sz 即可。

代码

#include<bits/stdc++.h>
#define int long long
#define inf (1ll << 62)
#define regint register int
#define pb push_back
#define mp make_pair
#define PII pair<int , int>
using namespace std;
const int MAXN = 2e5 + 10;
int t , q;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t --) {
        cin >> q;
        deque<int>Q;
        int num = 0 , ans = 0 , sz = 0;
        bool flag = false;
        while(q --) {
            int opt , k;
            cin >> opt;
            if(opt == 1) {
                if(flag) {
                    Q.push_back(Q.front());
                    ans = ans - Q.front() * sz + num;
                    Q.pop_front();
                } else {
                    Q.push_front(Q.back());
                    ans = ans - Q.back() * sz + num;
                    Q.pop_back();                   
                }
            } else if(opt == 2) {
                ans = (sz + 1) * num - ans;
                flag ^= true;
            } else {
                cin >> k;
                if(!flag) {
                    Q.push_back(k);
                    sz ++;
                    num += k;
                    ans += k * sz;
                } else {
                    Q.push_front(k);
                    sz ++;
                    num += k;
                    ans += k * sz;
                }
            }
            cout << ans << '\n';
        }
    }
    return 0;
}