Code:
#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\n",Ans[1]%mod); } return 0; }
