题解 CF2094G

题意

给定一个数组

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 值表示当前处于正方向还是反方向，每次采用该方向的方式维护双端队列即可。

程序如下

CPP

#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

相关推荐

评论

题解 CF2094G