题解 CF2094G

HYdroKomide · 2025-04-29 15:59:36 · 题解

题意

给定一个数组 a，有三类操作：翻转、循环移位和在末尾插入。每次操作后求 \sum_{i=0}^n a_i\cdot i。

思路

乍一看可能要高级数据结构维护，但其实所有操作都可以 O(1) 完成。

我们维护一个当前状态的答案 ans 和所有数组元素之和 sum，每次操作时如下更新即可：

• 操作一，ans\leftarrow \sum_{i=0}^{n-1}a_i-(n-1)\cdot a_n=ans+sum-a_n\cdot n；
• 操作二，ans\leftarrow n\cdot \sum_{i=0}^{n}a_i-ans=sum\cdot (n+1)-ans；
• 操作三，ans\leftarrow ans+(n+1)\cdot k;\ sum\leftarrow sum+k。

当然这是对答案的维护。对于数组本身的维护，显然不能直接使用数组暴力修改，考虑使用队列。而由于有翻转操作的存在，队列两端都可以增添元素，因此我们可以请出 STL 的好工具，双端队列 deque。

deque 支持从头部和尾部增添或者删除元素，维护一个 bool 值表示当前处于正方向还是反方向，每次采用该方向的方式维护双端队列即可。

程序如下

#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
int T,m;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&m);
        deque<int>q;
        bool inv=false;
        long long ans=0,sum=0;
        int n=0;
        while(m--){
            int op,x;
            scanf("%d",&op);
            if(op==1){
                int k;
                if(inv){
                    k=q.front();
                    q.pop_front();
                    q.push_back(k);
                }
                else{
                    k=q.back();
                    q.pop_back();
                    q.push_front(k);
                }
                ans=ans+sum-1ll*n*k;
            }
            else if(op==2){
                inv=!inv;
                ans=1ll*(n+1)*sum-ans;
            }
            else{
                scanf("%d",&x);
                if(inv)q.push_front(x);
                else q.push_back(x);
                ans+=1ll*++n*x;
                sum+=x;
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

THE END