[这是题目链接]: https://codeforces.com/contest/2094/problem/G

题意

定义炫酷值：一个长度为$m$的数组,$b[\ \ ]$的炫酷值为$\sum_{i=1}^mb_i\cdot i=b_1\cdot 1+b_2\cdot 2+b_3\cdot 3+\ldots + b_m\cdot m$

每组数据一开始为一个空数组$a[\ \ ]$，每次询问输入一个数$op$

  • op=1:$[a_1, a_2, \ldots, a_n]->[a_n, a_1, a_2, \ldots, a_{n-1}].$
  • op=2:$[a_1, a_2, \ldots, a_n]->[a_n, a_{n-1}, \ldots, a_1].$
  • op=3:输入一个数$k$,$[a_1, a_2, \ldots, a_n]->[a_1, a_2, \ldots, a_n, k]$

每次操作后输入此时数组的炫酷值。

思路

  • 对于操作1，有什么方法能够快速把数组进行转换呢？
    我们可以用deque存储数据，这样每次转换只需要把一头的数弹出然后放到另一头，效率很高。
  • 对于操作2，我们可以不对数组进行操作，而是用同时记录正向的炫酷值和一个反向的炫酷值，再用一个$bool$类型的变量rev进行记录翻转（翻转2次等于没翻转，所以用$bool$类型足够了），每次操作只要交换一下正向炫酷值和反向炫酷值并改变一下rev的状态即可。
  • 对于操作3，我们可以直接根据rev的情况决定是在双端队列的头还是尾部添加这个数，同时还需要一个变量sum来记录数组中所有元素的值，方便对反向炫酷值进行改变。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M =2e5+2;
int q;
deque<int> dq;
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T,t;
    cin>>T;
    while(T--)
    {
        dq.clear();
        cin>>q;
        int op;
        bool rev=0;
        int sum=0,ans=0,rans=0,siz=0;
        while(q--)
        {
            cin>>op;
            if(op==1)
            {
                if(rev)
                {
                    int t=dq.front();
                    dq.pop_front();
                    dq.push_back(t);
                    ans-=t*siz;
                    rans-=t;
                    ans+=sum-t;
                    rans-=sum-t;
                    ans+=t;
                    rans+=t*siz;
                }
                else
                {
                    int t=dq.back();
                    dq.pop_back();
                    dq.push_front(t);
                    ans-=t*siz;
                    rans-=t;
                    ans+=sum-t;
                    rans-=sum-t;
                    ans+=t;
                    rans+=t*siz;
                }
            }
            else if(op==2)
            {
                rev=rev==0? 1:0;
                swap(ans,rans);
            }
            else
            {
                siz++;
                cin>>t;
                if(rev)
                {
                    ans+=siz*t;
                    rans+=sum+t;
                    dq.push_front(t);
                }
                else
                {
                    ans+=siz*t;
                    rans+=sum+t;
                    dq.push_back(t);
                }
                sum+=t;
            }   
            cout<<ans<<'\n';
        }
    }
    return 0;
}