BZOJ 4597: [Shoi2016]随机序列

4597: [Shoi2016]随机序列

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 255 Solved: 174
[Submit][Status][Discuss]

Description

你的面前有N个数排成一行。分别为A1, A2, … , An。你打算在每相邻的两个 Ai和 Ai+1 间都插入一个加号或者

减号或者乘号。那么一共有 3^(n-1) 种可能的表达式。你对所有可能的表达式的值的和非常感兴趣。但这毕竟太

简单了，所以你还打算支持一个修改操作，可以修改某个Ai 的值。你能够编写一个程序对每个修改都输出修改完

之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是

在最初的表达式上进行。

Input

第一行包含 2 个正整数 N 和 Q，为数的个数和询问的个数。

接下来一行 n 个非负整数，依次表示a1,a2...an

在接下来 Q 行，其中第 ?? 行两个非负整数Ti 和Vi，表示要将 A_ti 修改为 Vi。其中 1 ≤ Ti ≤ N。

保证对于 1 ≤ J ≤ N, 1 ≤ i≤ Q，都有 Aj,Vi ≤ 10^4。

N,Q<=100000,本题仅有三组数据

Output

输出共 Q 行，其中第 i 行表示第 i 个询问之后所有可能表达式的和，对10^9 + 7 取模。

Sample Input

5 5
9384 887 2778 6916 7794
2 8336
5 493
3 1422
1 28
4 60

Sample Output

890543652
252923708
942282590
228728040
608998099

题解：

　　推一下式子，或者打一下表就可以发现+,-的都会抵消，只有和a1连在一起的乘发才产生贡献，并且对于a1*a2*a3……*an而言他前面的系数为3^(len-1-n)*2，（注意特判n==len的情况）。

　　那么我们考虑用线段树来维护这个式子，每个叶子节点就是一个前缀积*他前面的系数，线段树维护区间和，每次对于x进行点修改，就相当于修改x~n的这一段区间，写一个lazy就可以了。

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define ll long long
#define MAXN 100100
#define mod 1000000007
using namespace std;
struct tree{
    int l,r;ll lz,sum;
}a[MAXN*4];
ll v[MAXN],vv[MAXN],pw[MAXN];
int n,q;
 
void pushup(int xv){
    a[xv].sum=a[xv*2].sum+a[xv*2+1].sum;
    //a[xv].sum%=mod;
    if(a[xv].sum>=mod) a[xv].sum-=mod;
}
 
void build(int xv,int l,int r){
    if(l==r){
        a[xv].l=l,a[xv].r=r,a[xv].lz=1;
        if(l==n)    a[xv].sum=v[l];
        else a[xv].sum=2*v[l]*pw[n-1-l]%mod;
        return;
    }
    a[xv].l=l,a[xv].r=r,a[xv].lz=1;
    int mid=(l+r)/2;
    build(xv*2,l,mid),build(xv*2+1,mid+1,r);
    pushup(xv);
}
 
ll ni(ll bas,ll ti){
    ll ans=1;
    while(ti){
        if(ti&1) ans=(ans*bas)%mod;
        bas=(bas*bas)%mod;ti>>=1;
    }
    return ans;
}
 
void pushdown(int xv){
    if(a[xv].lz==1) return;
    a[xv*2].sum=(a[xv*2].sum*a[xv].lz)%mod;
    a[xv*2+1].sum=(a[xv*2+1].sum*a[xv].lz)%mod;
    a[xv*2].lz=(a[xv*2].lz*a[xv].lz)%mod;
    a[xv*2+1].lz=(a[xv*2+1].lz*a[xv].lz)%mod;
    a[xv].lz=1;
}
 
void change(int xv,int l,int r,ll x){
    int L=a[xv].l,R=a[xv].r,mid=(L+R)/2;
    if(l==L&&R==r){
        a[xv].sum=a[xv].sum*x%mod;
        a[xv].lz=a[xv].lz*x%mod;
        return;
    }
    pushdown(xv);
    if(r<=mid) change(xv*2,l,r,x);
    else if(l>mid) change(xv*2+1,l,r,x);
    else change(xv*2,l,mid,x),change(xv*2+1,mid+1,r,x);
    pushup(xv);
}
 
int main()
{
    scanf("%d%d",&n,&q);
    v[0]=1;for(int i=1;i<=n;i++) scanf("%lld",&v[i]),vv[i]=v[i],v[i]=(v[i]*v[i-1])%mod;
    pw[0]=1;for(int i=1;i<=n;i++) pw[i]=pw[i-1]*3,pw[i]%=mod;
    build(1,1,n);
    while(q--){
        int ps,x;scanf("%d%d",&ps,&x);
        ll xx=(x*ni(vv[ps],mod-2))%mod;
        vv[ps]=x;
        change(1,ps,n,xx);
        printf("%lld
",a[1].sum);
    }
    return 0;
}