首页 > 代码库 > 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 随机序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。