【bzoj4597】 [Shoi2016]随机序列

可以发现加减号之间可以互相抵消.

真正加到答案里的只有一些前缀积.

记s[i]为a[1]*a[2]*a[3]...*a[i].那s[i]在答案中出现的次数就是2*3^(n-i-1);

修改一个数只会对后面的数有影响.

预处理逆元然后用线段树维护即可.

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 100010

#define P 1000000007

using namespace std;

long long t[N<<2],inv[N],a[N],s[N],bin[N],x,p[N<<2];

int n,q,pos;

void build(int k,int l,int r){

  int mid=(l+r)>>1;

  if (l==r){

    if (l!=n) t[k]=(s[l]*bin[n-l-1]*2)%P;

    else t[k]=s[l];

    return;

  }

  build(k<<1,l,mid);

  build(k<<1|1,mid+1,r);

  t[k]=(t[k<<1]+t[k<<1|1])%P;

}

void paint(int k,long long v){

  t[k]=(t[k]*v)%P;

  p[k]=(p[k]*v)%P;

}

void pushdown(int k,int l,int r){

   int mid=(l+r)>>1;

   paint(k<<1,p[k]);

   paint(k<<1|1,p[k]);

   p[k]=1;

}

void change(int k,int l,int r,int ll,int rr,long long v){

  int mid=(l+r)>>1;

  if (ll<=l&&r<=rr){paint(k,v);return;}

  if (p[k]!=1) pushdown(k,l,r);

  if (ll<=mid) change(k<<1,l,mid,ll,rr,v);

  if (mid<rr) change(k<<1|1,mid+1,r,ll,rr,v);

  t[k]=(t[k<<1]+t[k<<1|1])%P;

}

int main(){

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

  for (int i=1;i<=n;i++) scanf("%lld",&a[i]);

  bin[0]=1;

  for (int i=1;i<=n;i++) bin[i]=(bin[i-1]*3)%P;

  inv[1]=1;

   for(int i=2;i<=10000;i++)

        inv[i]=(P-(long long)P/i*inv[P%i]%P);

  s[1]=a[1];

  for (int i=2;i<=n;i++) s[i]=(s[i-1]*a[i])%P;

  build(1,1,n);

  for (int i=1;i<=n*2;i++) p[i]=1;

  for (int i=1;i<=q;i++){

    scanf("%d%lld",&pos,&x);

    change(1,1,n,pos,n,x*inv[a[pos]]%P);

    a[pos]=x;printf("%lld\n",t[1]);

  }

}