给出n个数的序列A，相邻两个数之间随机出现加号、减号和乘号。m次操作，每次修改一个数，然后输出所有可能的序列答案之和模1,000,000,007的值。
n,q≤100000
考虑一段连续乘在一起的数（包括只有一个数的情况），如果它不包括第一个数，即前面可能会有加号、减号，那么它对答案的贡献为0（加减抵消掉了）。所以有用的只有从第一个数开始连续乘起来的一段。 枚举第一个加或减号出现在第i个数之后，然后它对答案的贡献就是左边的数累乘，再乘3的幂乘2（i=n不用乘）。然后修改一个数会让一个后缀区间的数都乘上一个数。 用线段树维护区间和即可。 时间复杂度 O(nlogn)
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=100005,mo=1e9+7,M=262200; typedef long long LL; int n,q,s[N],p[N],Inv[N],a[N],t[M],tag[M]; char c; int read() { int x=0,sig=1; for (c=getchar();c<'0' || c>'9';c=getchar()) if (c=='-') sig=-1; for (;c>='0' && c<='9';c=getchar()) x=x*10+c-48; return x*sig; } void Init(int l,int r,int x) { tag[x]=1; if (l==r) { t[x]=s[l]; return; } int mid=l+r>>1; Init(l,mid,x<<1); Init(mid+1,r,x<<1|1); t[x]=(t[x<<1]+t[x<<1|1])%mo; } void change(int l,int r,int a,int b,int v,int x) { if (l==a && r==b) { t[x]=(LL)t[x]*v%mo; tag[x]=(LL)tag[x]*v%mo; return; } if (tag[x]!=1) { t[x<<1]=(LL)t[x<<1]*tag[x]%mo; tag[x<<1]=(LL)tag[x<<1]*tag[x]%mo; t[x<<1|1]=(LL)t[x<<1|1]*tag[x]%mo; tag[x<<1|1]=(LL)tag[x<<1|1]*tag[x]%mo; tag[x]=1; } int mid=l+r>>1; if (b<=mid) change(l,mid,a,b,v,x<<1); else if (a>mid) change(mid+1,r,a,b,v,x<<1|1); else { change(l,mid,a,mid,v,x<<1); change(mid+1,r,mid+1,b,v,x<<1|1); } t[x]=(t[x<<1]+t[x<<1|1])%mo; } int main() { n=read(); q=read(); p[0]=1; for (int i=1;i<=n;i++) { a[i]=read(); p[i]=(LL)p[i-1]*a[i]%mo; } s[n]=p[n]; for (int i=n-1,j=1;i;i--,j=(LL)j*3%mo) { s[i]=(LL)j*2*p[i]%mo; } Init(1,n,1); Inv[1]=1; for (int i=2;i<N;i++) Inv[i]=(LL)Inv[mo%i]*(mo-mo/i)%mo; while (q--) { int x=read(),v=read(); change(1,n,x,n,(LL)v*Inv[a[x]]%mo,1); a[x]=v; printf("%d\n",t[1]); } return 0; }