! JLOI/SHOI2016随机序列

考虑性质

(n1e5)

SOL：

(a_1*a_2+a_3*a_4-a_5)

(a_1*a_2-a_3*a_4+a_5)

上式相加只剩前面的乘法，所以我们要算的是所有前缀积

(ans=sum_{i=1}^{n-1}s_i*2*3^{n-i-1}+s_n,s_i=prod_{j=1}^ia_j)

但(a_i)可能为0，所以不能算逆元

重点：

(mul_p=mul_{lc}*mul_{rc})

(ans_p=ans_{lc}+mul_{lc}*ans_{rc})

(mul)为区间乘积，(ans)为区间答案，(ans_1)即为最后答案

线段树

时间复杂度(O(nlog_n))

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
#define ll long long
#define lc (p<<1)
#define rc (p<<1|1)
const int N=1e5+4,mod=1e9+7;
int n,Q,ans[N<<2],mul[N<<2],a[N],pw[N];
inline void newnode(int p,int l){
	mul[p]=a[l];
	if(l==n)ans[p]=a[l];
	else ans[p]=(ll)a[l]*2*pw[n-l-1]%mod;
}
inline void pushup(int p){
	ans[p]=((ll)mul[lc]*ans[rc]+ans[lc])%mod;
	mul[p]=(ll)mul[lc]*mul[rc]%mod;
}
void build(int p,int l,int r){
	if(l==r){newnode(p,l);return;}
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(p); 
}
void modify(int p,int l,int r,int x){
	if(l==r){newnode(p,l);return;}
	int mid=l+r>>1;
	if(x<=mid)modify(lc,l,mid,x);
	else modify(rc,mid+1,r,x);
	pushup(p);
}
int main(){
	n=read();Q=read();
	for(int i=1;i<=n;i++)a[i]=read();
	pw[0]=1;
	for(int i=1;i<=n;i++)pw[i]=3ll*pw[i-1]%mod;
	build(1,1,n);
	while(Q--){
		static int x;
		x=read();a[x]=read();
		modify(1,1,n,x);
		cout<<ans[1]<<"
";
	} 
	return (0-0);
}