P4340 [SHOI2016]随机序列

题目

思维好题

做法

是否觉得水在于你是否发现加减是会抵消的，所以我们只用考虑乘的部分

一块乘只能前面无号(也就是前缀形式)才统计，所以用线段树维护区间前缀乘就行了

My complete code

#include<cstdio>

#include<cstring>

#include<string>

#include<iostream>

#include<string>

#include<algorithm>

using namespace std;

typedef long long LL;

const LL maxn=3000000,p=1e9+7;

inline LL Read(){

    LL x(0),f(1);char c=getchar();

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

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*f;

}

inline LL Pow(LL base,LL b){

	LL ret(1);

	while(b){

		if(b&1) ret=ret*base%p;

		base=base*base%p,b>>=1;

	}return ret;

}

LL root,nod,n,m,a[maxn];

LL lazy[maxn],sum[maxn],s[maxn],pw[maxn],son[maxn][2];

void Build(LL &now,LL l,LL r){

	now=++nod; lazy[now]=1;

	if(l==r){

	    if(l!=n)

		    sum[now]=s[l]*2*pw[n-l-1]%p;

		else sum[now]=s[l];

		return;

	}

	LL mid(l+r>>1);

	Build(son[now][0],l,mid),Build(son[now][1],mid+1,r);

	sum[now]=(sum[son[now][0]]+sum[son[now][1]])%p;

}

inline void Pushdown(LL now){

	LL lc(son[now][0]),rc(son[now][1]);

	if(lazy[now]!=1){

		lazy[lc]=lazy[lc]*lazy[now]%p;

		lazy[rc]=lazy[rc]*lazy[now]%p;

		sum[lc]=sum[lc]*lazy[now]%p,sum[rc]=sum[rc]*lazy[now]%p;

		lazy[now]=1;

	}

}

void Change_m(LL now,LL l,LL r,LL lt,LL rt,LL val){

	if(lt<=l&&rt>=r){

		sum[now]=sum[now]*val%p;

		lazy[now]=lazy[now]*val%p;

		return;

	}Pushdown(now);

	LL mid(l+r>>1);

	if(lt<=mid) Change_m(son[now][0],l,mid,lt,rt,val);

	if(rt>mid) Change_m(son[now][1],mid+1,r,lt,rt,val);

	sum[now]=(sum[son[now][0]]+sum[son[now][1]])%p;

}

int main(){

	n=Read(),m=Read();

	s[0]=pw[0]=1;

	for(LL i=1;i<=n;++i)

	    a[i]=Read()%p,

		s[i]=s[i-1]*a[i]%p,

	    pw[i]=pw[i-1]*3%p;

	Build(root,1,n);

	while(m--){

		LL x(Read()),val(Read());

		Change_m(root,1,n,x,n,val*Pow(a[x],p-2)%p);

		a[x]=val;

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

	}return 0;

}

巴特西

P4340 [SHOI2016]随机序列

题目

做法

My complete code

最新文章

热门文章