首页 > 代码库 > BZOJ 4597 随机序列

BZOJ 4597 随机序列

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

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

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 100500#define mod 1000000007using namespace std;long long n,q,table[maxn],a[maxn],x,y;long long root,tot=0,ls[maxn<<2],rs[maxn<<2],sum1[maxn<<2],sum2[maxn<<2];void get_table(){    table[0]=1;    for (long long i=1;i<=100000;i++)        table[i]=(table[i-1]*3)%mod;}void pushup(long long now,long long left,long long right){    long long mid=(left+right)>>1;    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-1])%mod*2)%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)>>1;    build(ls[now],left,mid);    build(rs[now],mid+1,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)>>1;    if (pos<=mid) modify(ls[now],left,mid,pos,x);    else modify(rs[now],mid+1,right,pos,x);    pushup(now,left,right);}int main(){    scanf("%lld%lld",&n,&q);    for (long long i=1;i<=n;i++)        scanf("%lld",&a[i]);    get_table();    build(root,1,n);    for (long long i=1;i<=q;i++)    {        scanf("%lld%lld",&x,&y);        modify(root,1,n,x,y);        printf("%lld\n",sum1[root]%mod);    }    return 0;}

 

BZOJ 4597 随机序列