首页 > 代码库 > 【分块】bzoj1798 [Ahoi2009]Seq 维护序列seq
【分块】bzoj1798 [Ahoi2009]Seq 维护序列seq
分块，打标记，维护两个标记：乘的 和 加的。
每次 区间乘的时候，对 乘标记 和 加标记 都 乘上那个值。
每次 区间加的时候 对 加标记 加上那个值。
(ax+b)*v=axv+bv。开 long long。
1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 typedef long long ll; 5 int n,sum,sz,num[100001],l[350],r[350],x,y,m,op; 6 ll MOD,a[100001],sumv[350],lzy1[350],lzy2[350],v; 7 void makeblock() 8 { 9 sz=sqrt(n); if(!sz) sz=1; 10 for(sum=1;sum*sz<n;sum++) 11 { 12 l[sum]=r[sum-1]+1; r[sum]=sum*sz; 13 for(int i=l[sum];i<=r[sum];++i) 14 { 15 num[i]=sum; 16 sumv[sum]=(sumv[sum]+a[i])%MOD; 17 } 18 } 19 l[sum]=r[sum-1]+1; r[sum]=n; 20 for(int i=l[sum];i<=r[sum];++i) 21 { 22 num[i]=sum; 23 sumv[sum]=(sumv[sum]+a[i])%MOD; 24 } 25 for(int i=1;i<=sum;++i) lzy1[i]=1; 26 } 27 void pushdown(const int &p) 28 { 29 if(lzy1[p]!=1 || lzy2[p]) 30 { 31 for(int i=l[p];i<=r[p];++i) 32 a[i]=(a[i]*lzy1[p]+lzy2[p])%MOD; 33 lzy1[p]=1; lzy2[p]=0; 34 } 35 } 36 void work1(const int &L,const int &R) 37 { 38 sumv[num[L]]=0; 39 for(int i=L;i<=R;++i) a[i]=(a[i]*v)%MOD; 40 for(int i=l[num[L]];i<=r[num[L]];++i) 41 sumv[num[L]]=(sumv[num[L]]+a[i])%MOD; 42 } 43 void update1() 44 { 45 pushdown(num[x]); pushdown(num[y]); 46 if(num[x]==num[y]) work1(x,y); 47 else 48 { 49 work1(x,r[num[x]]); work1(l[num[y]],y); 50 for(int i=num[x]+1;i<num[y];++i) 51 { 52 lzy1[i]=(lzy1[i]*v)%MOD; 53 lzy2[i]=(lzy2[i]*v)%MOD; 54 sumv[i]=(sumv[i]*v)%MOD; 55 } 56 } 57 } 58 void work2(const int &L,const int &R) 59 { 60 for(int i=L;i<=R;++i) a[i]=(a[i]+v)%MOD; 61 sumv[num[L]]=(sumv[num[L]]+(ll)(R-L+1)*v)%MOD; 62 } 63 void update2() 64 { 65 pushdown(num[x]); pushdown(num[y]); 66 if(num[x]==num[y]) work2(x,y); 67 else 68 { 69 work2(x,r[num[x]]); work2(l[num[y]],y); 70 for(int i=num[x]+1;i<num[y];++i) 71 { 72 lzy2[i]=(lzy2[i]+v)%MOD; 73 sumv[i]=(sumv[i]+(ll)sz*v)%MOD; 74 } 75 } 76 } 77 void query() 78 { 79 pushdown(num[x]); pushdown(num[y]); ll ans=0; 80 if(num[x]==num[y]) {for(int i=x;i<=y;++i) ans=(ans+a[i])%MOD;} 81 else 82 { 83 for(int i=x;i<=r[num[x]];++i) ans=(ans+a[i])%MOD; 84 for(int i=l[num[y]];i<=y;++i) ans=(ans+a[i])%MOD; 85 for(int i=num[x]+1;i<num[y];++i) ans=(ans+sumv[i])%MOD; 86 } printf("%d\n",(int)ans); 87 } 88 int main() 89 { 90 scanf("%d%lld",&n,&MOD); 91 for(int i=1;i<=n;++i) scanf("%lld",&a[i]); 92 makeblock(); scanf("%d",&m); 93 for(;m>0;--m) 94 { 95 scanf("%d%d%d",&op,&x,&y); 96 if(op==1) {scanf("%lld",&v); update1();} 97 else if(op==2) {scanf("%lld",&v); update2();} 98 else query(); 99 }100 return 0;101 }
【分块】bzoj1798 [Ahoi2009]Seq 维护序列seq
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。