Description
你的面前有N个数排成一行。分别为A1, A2, … , An。你打算在每相邻的两个 Ai和 Ai+1 间都插入一个加号或者
减号或者乘号。那么一共有 3^(n-1) 种可能的表达式。你对所有可能的表达式的值的和非常感兴趣。但这毕竟太
简单了，所以你还打算支持一个修改操作，可以修改某个Ai 的值。你能够编写一个程序对每个修改都输出修改完
之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行， 而不是
在最初的表达式上进行。
Input
第一行包含 2 个正整数 N 和 Q，为数的个数和询问的个数。
接下来一行 n 个非负整数，依次表示a1,a2...an
在接下来 Q 行，其中第 ?? 行两个非负整数Ti 和Vi，表示要将 Ati 修改为 Vi。其中 1 ≤ Ti ≤ N。
保证对于 1 ≤ J ≤ N, 1 ≤ i≤ Q，都有 Aj,Vi ≤ 10^4。
N,Q<=100000,本题仅有三组数据
Output
输出共 Q 行，其中第 i 行表示第 i 个询问之后所有可能表达式的和，对10^9 + 7 取模。
有贡献的一定是从序列的头开始连续一段的乘积.
因为如果有 $+$ 或 $-$ 的话一定能被另一种符号抵消掉.
那么，对于 $1$~$l$ 来说，贡献是 $2 imes 3^{n-l-1} imes prod_{i=1}^{l}A_{i}$
因为 $l$ 后面的符号肯定是 $+$ 或 $-$ ，而 $l+1$ 后面的符号就随便选了.
直接用线段树维护这个就行.
即 $sum_{l=1}^{n}2 imes 3^{n-l-1} imesprod_{i=1}^{l}A_{i}$.
细节什么的就注意一下.
#include <bits/stdc++.h>
using namespace std;
namespace IO {
void setIO(string s) {
string in=s+".in";
freopen(in.c_str(),"r",stdin);
}
};
typedef long long ll;
const int maxn=100004;
const ll mod=1000000007;
int n,m;
ll A[maxn],mul[maxn*4],Ans[maxn*4],qpow[maxn];
void pushup(int x) {
mul[x]=mul[x<<1]*mul[(x<<1)|1]%mod;
Ans[x]=(Ans[x<<1]+mul[x<<1]*Ans[(x<<1)|1]%mod)%mod;
}
void build(int l,int r,int now) {
if(l==r) {
mul[now]=A[l];
if(l==n) Ans[now]=A[l];
else Ans[now]=A[l]*1ll*2*qpow[n-l-1]%mod;
return;
}
int mid=(l+r)>>1;
build(l,mid,now<<1);
build(mid+1,r,(now<<1)|1);
pushup(now);
}
void update(int l,int r,int now,int p,int v) {
if(l==r) {
A[l]=1ll*v;
mul[now]=A[l];
if(l==n) Ans[now]=A[l];
else Ans[now]=A[l]*1ll*2*qpow[n-l-1]%mod;
return;
}
int mid=(l+r)>>1;
if(p<=mid) update(l,mid,now<<1,p,v);
else update(mid+1,r,(now<<1)|1,p,v);
pushup(now);
}
int main() {
using namespace IO;
// setIO("input");
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",&A[i]);
qpow[0]=mul[0]=Ans[0]=1;
for(int i=1;i<=n+2;++i) qpow[i]=qpow[i-1]*3%mod;
build(1,n,1);
for(int cas=1;cas<=m;++cas) {
int t,v;
scanf("%d%d",&t,&v);
update(1,n,1,t,v);
printf("%lld
",Ans[1]%mod);
}
return 0;
}