NC220348. D动态序列
描述
给出n（1 <= n <= 100000）个整数 ai（1 <= ai <= 1000000000）的序列，有q（1 <= q <= 100000）个询问，设序列长度为len，序号从1开始，每个询问有如下操作：
1 b：序列中所有数乘以整数b（1 <= b <= 1000000000）
2 b：序列中所有数增加整数b（1 <= b <= 1000000000）
3 b：在序列头部添加一个整数b（1 <= b <= 1000000000）
4 b：在序列尾部添加一个整数b（1 <= b <= 1000000000）
5 p：输出序列的第p（1 <= p <= len）个数，并将结果对1000000007取模
题目保证所有操作都是合法的！
输入描述
第1行两个整数n、q，第2行n个整数，代表初始序列，第3行及之后，每一行都有一个询问，总共有q行，询问格式参见题目描述和样例
输出描述
对于询问5，输出对应位置的数
示例1
输入:
5 5 1 2 3 4 5 1 2 2 1 3 1 4 2 5 3
输出:
5
说明:
样例解释:
刚开始的序列：1 2 3 4 5
执行完操作1：2 4 6 8 10
执行完操作2：3 5 7 9 11
执行完操作3：1 3 5 7 9 11
执行完操作4：1 3 5 7 9 11 2
执行操作5：当前序列第3个数是5，所以输出5
C++(clang++11) 解法, 执行用时: 156ms, 内存消耗: 3220K, 提交时间: 2021-03-28 21:40:03
#include<iostream>
using namespace std;
const int mod=1000000007,N=100005;
int A[3*N],l=100000,r,n,q,c,o,mul=1,add=0;
int qmi(int a,int b)
{
if(b==0) return 1%mod;
return 1ll*(b&1?a:1)*qmi(1ll*a*a%mod,b>>1)%mod;
}
int main()
{
cin>>n>>q;r=l+n-1;
for(int i=l;i<=r;++i) cin>>A[i];
while(q--){
cin>>c>>o;
if(c==1) mul=1ll*mul*o%mod,add=1ll*add*o%mod;
else if(c==2) add=(0ll+add+o)%mod;
else if(c==3) A[--l]=(1ll*(o-add)*qmi(mul,mod-2)%mod+mod)%mod;
else if(c==4) A[++r]=(1ll*(o-add)*qmi(mul,mod-2)%mod+mod)%mod;
else cout<<(1ll*mul*A[l+o-1]%mod+add)%mod<<endl;
}
return 0;
}