蠢了蠢了

首先连续的乘法可以构成一个连通块

现在有三个连通块$a,b,c$

观察$a?b?c$,发现一种状态下的$b,c$,对答案的贡献,总能被取相反状态(减变加,加变减)的$b,c$给抵消掉。

因此只需要统计$a$,也就是前缀积,枚举每一种前缀积出现的次数,统计起来即为答案。

即$(\sum\limits_{i=1}^{n-1}S_i*3^{n-i-1}*2)+S_n$

$*2$是代表$i,i+1$只能选$+,-$。

修改的时候,打个懒标记下传就好了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=1e5+5,mod=1e9+7;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
inline int add(int x,int y){x+=y;if(x>=mod)x-=mod;return x;}
inline int del(int x,int y){x-=y;if(x<0)x+=mod;return x;}
inline int mul(int x,int y){x=1ll*x*y%mod;return x;}
inline int fpow(int a,int b){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;}
struct node{int s,cd,l,r;}t[N<<2];int sum[N];int n,m;
void update(int p){t[p].s=add(t[p<<1].s,t[p<<1|1].s);}
void pushdown(int p)
{
    if(t[p].cd!=1)
    {
        t[p<<1].cd=mul(t[p<<1].cd,t[p].cd);t[p<<1|1].cd=mul(t[p<<1|1].cd,t[p].cd);
        t[p<<1].s=mul(t[p<<1].s,t[p].cd),t[p<<1|1].s=mul(t[p<<1|1].s,t[p].cd);
        t[p].cd=1;
    }
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;t[p].cd=1;
    if(l==r){if(l!=n)t[p].s=mul(2*fpow(3,n-1-l),sum[l]);else t[p].s=sum[l];return ;}
    int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    update(p);
}
void change(int p,int L,int R,int cd)
{
    if(L<=t[p].l&&R>=t[p].r){t[p].cd=mul(t[p].cd,cd),t[p].s=mul(t[p].s,cd);return ;}
    pushdown(p);int mid=t[p].l+t[p].r>>1;
    if(L<=mid)change(p<<1,L,R,cd);
    if(R>mid)change(p<<1|1,L,R,cd);
    update(p);
}
int query(int p,int L,int R)
{
    if(L<=t[p].l&&R>=t[p].r)return t[p].s;
    pushdown(p);int mid=t[p].l+t[p].r>>1,val=0;
    if(L<=mid)val=add(val,query(p<<1,L,R));
    if(R>mid)val=add(val,query(p<<1|1,L,R));
    return val;
}
int a[N];
int main()
{
    qr(n),qr(m);sum[0]=1;
    for(int i=1;i<=n;i++)qr(sum[i]),a[i]=sum[i],sum[i]=mul(sum[i],sum[i-1]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int pos,x;qr(pos),qr(x);
        int w=mul(x,fpow(a[pos],mod-2));
        a[pos]=x;change(1,pos,n,w);
        int ans=query(1,1,n);qw(ans);puts("");
    }
    return 0;
}