BZOJ-4597: [Shoi2016]随机序列

Description

你的面前有N个数排成一行。分别为A1, A2, … , An。你打算在每相邻的两个 Ai和 Ai+1 间都插入一个加号或者减号或者乘号。那么一共有 3^(n-1) 种可能的表达式。你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了，所以你还打算支持一个修改操作，可以修改某个Ai 的值。你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行， 而不是在最初的表达式上进行。N,Q<=100000

发现最后的答案即为所有前缀乘积的和，符合区间加法，线段树维护一下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
#define N 101000 
int n,m,a[N];
ll s[N<<2],w[N<<2],p[N];
void pushup(int pos,int x)
{
    s[pos]=s[pos<<1]*s[pos<<1|1]%mod;
    w[pos]=((w[pos<<1]-s[pos<<1]+mod)%mod*p[x]%mod
        +s[pos<<1]*2*p[x-1]%mod
        +s[pos<<1]*w[pos<<1|1])%mod;
}
void build(int pos,int l,int r)
{
    if(l==r){w[pos]=s[pos]=a[l]; return ;}
    int mid=(l+r)>>1;
    build(pos<<1,l,mid);
    build(pos<<1|1,mid+1,r);
    pushup(pos,r-mid);
}
void fix(int pos,int l,int r,int x,int y)
{
    if(l==r) {w[pos]=s[pos]=y; return ;}
    int mid=(l+r)>>1;
    if(x<=mid) fix(pos<<1,l,mid,x,y);
    else fix(pos<<1|1,mid+1,r,x,y);
    pushup(pos,r-mid);
}
int main()
{
    scanf("%d%d",&n,&m);
    int i;
    for(i=1;i<=n;++i) scanf("%d",a+i);
    for(p[0]=1,i=1;i<=n;++i) p[i]=p[i-1]*3%mod;
    build(1,1,n); int x,y;
    while(m--)
    {
        scanf("%d%d",&x,&y);
        fix(1,1,n,x,y);
        printf("%lld\n",w[1]);
    }
    return 0;
}