【BZOJ4597】[Shoi2016]随机序列 线段树

时间：2023-12-28 19:16:14

【BZOJ4597】[Shoi2016]随机序列

Description

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

Input

第一行包含 2 个正整数 N 和 Q，为数的个数和询问的个数。
接下来一行 n 个非负整数，依次表示a1,a2...an
在接下来 Q 行，其中第 ?? 行两个非负整数Ti 和Vi，表示要将 Ati 修改为 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

题解：+号和-号就是逗你玩的，因为如果把+换成-，那么对应位置的值就会变成相反数，最后都会抵消，所以只有一开始的连续的一段乘号是有用的。

所以用s[i]表示前缀乘积，答案可以表示成$\sum\limits_{i=1}^{n-1}s[i]*3^{n-i-1}*2+s[n]$（注意最后一个不*2），用线段树维护一下即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#define lson x<<1

#define rson x<<1|1

using namespace std;

typedef long long ll;

const ll P=1000000007;

const int maxn=100010;

int n,m;

ll A[maxn],v[maxn],s[maxn<<2],ts[maxn<<2];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

inline ll pm(ll x,ll y)

{

	ll z=1;

	while(y)

	{

		if(y&1)	z=z*x%P;

		x=x*x%P,y>>=1;

	}

	return z;

}

void build(int l,int r,int x)

{

	if(l==r)

	{

		s[x]=v[l];

		return ;

	}

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

	build(l,mid,lson),build(mid+1,r,rson);

	ts[x]=1,s[x]=(s[lson]+s[rson])%P;

}

void updata(int l,int r,int x,int a,int b,ll c)

{

	if(a<=l&&r<=b)

	{

		s[x]=s[x]*c%P,ts[x]=ts[x]*c%P;

		return ;

	}

	if(ts[x]!=1)

	{

		s[lson]=s[lson]*ts[x]%P,s[rson]=s[rson]*ts[x]%P,ts[lson]=ts[lson]*ts[x]%P,ts[rson]=ts[rson]*ts[x]%P;

		ts[x]=1;

	}

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

	if(a<=mid)	updata(l,mid,lson,a,b,c);

	if(b>mid)	updata(mid+1,r,rson,a,b,c);

	s[x]=(s[lson]+s[rson])%P;

}

int main()

{

	n=rd(),m=rd();

	int i,a,b;

	ll tmp=1;

	for(i=1;i<=n;i++)	A[i]=v[i]=rd();

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

	for(i=n-1;i>=1;i--)	v[i]=(v[i]*tmp<<1)%P,tmp=tmp*3%P;

	build(1,n,1);

	for(i=1;i<=m;i++)

	{

		a=rd(),b=rd();

		updata(1,n,1,a,n,b*pm(A[a],P-2)%P),A[a]=b;

		printf("%lld\n",s[1]);

	}

	return 0;

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

相关文章