BZOJ 4597 随机序列

一定要想到，对于一个空位如果填了+，那么一定有一个表达式这里填-号使得后面的全部抵消掉。这点十分重要。

于是发现这个答案只和前缀积有关，线段树维护即可。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100500

#define mod 1000000007

using namespace std;

long long n,q,table[maxn],a[maxn],x,y;

long long root,tot=,ls[maxn<<],rs[maxn<<],sum1[maxn<<],sum2[maxn<<];

void get_table()

{

    table[]=;

    for (long long i=;i<=;i++)

        table[i]=(table[i-]*)%mod;

}

void pushup(long long now,long long left,long long right)

{

    long long mid=(left+right)>>;

    long long ret1,ret2,ret3;

    ret1=((sum1[ls[now]]-sum2[ls[now]])+mod);

    ret2=sum2[ls[now]];

    ret3=sum1[rs[now]];

    sum1[now]=(((ret1*table[right-mid])%mod+((ret2*table[right-mid-])%mod*)%mod)%mod+(ret3*ret2)%mod)%mod;

    sum2[now]=(sum2[ls[now]]*sum2[rs[now]])%mod;

}

void build(long long &now,long long left,long long right)

{

    now=++tot;

    if (left==right)

    {

        sum1[now]=sum2[now]=a[left]%mod;

        return;

    }

    long long mid=(left+right)>>;

    build(ls[now],left,mid);

    build(rs[now],mid+,right);

    pushup(now,left,right);

}

void modify(long long now,long long left,long long right,long long pos,long long x)

{

    if (left==right)

    {

        sum1[now]=sum2[now]=x%mod;

        return;

    }

    long long mid=(left+right)>>;

    if (pos<=mid) modify(ls[now],left,mid,pos,x);

    else modify(rs[now],mid+,right,pos,x);

    pushup(now,left,right);

}

int main()

{

    scanf("%lld%lld",&n,&q);

    for (long long i=;i<=n;i++)

        scanf("%lld",&a[i]);

    get_table();

    build(root,,n);

    for (long long i=;i<=q;i++)

    {

        scanf("%lld%lld",&x,&y);

        modify(root,,n,x,y);

        printf("%lld\n",sum1[root]%mod);

    }

    return ;

}