[BZOJ 1798]维护序列
转载请注明出处:http://danihao123.is-programmer.com/
万年不更的zzs出现了……
这个题以前竟然没做……近几天做了一下,首交竟然unAC……看样子是我真不会线段树了。
这题不难,唯一需要注意的是乘法标记对加法标记也有影响,而且下传要乘法优先。
代码(警告:此代码exciting):
/************************************************************** Problem: 1798 User: danihao123 Language: C++ Result: Accepted Time:7696 ms Memory:10980 kb ****************************************************************/ #include <cstdio> typedef long long ll; const int maxn=100005; ll ha; struct Node{ ll sumv; int L,R; ll addv,mulv; Node *lc,*rc; Node(ll v,int pos){ sumv=v%ha; addv=0; mulv=1; L=R=pos; lc=rc=NULL; } Node(Node *l,Node *r,int Le,int Ri){ sumv=0; addv=0; mulv=1; L=Le; R=Ri; lc=l; rc=r; } void paint_add(ll v){ v=v%ha; addv=(addv+v)%ha; ll add_v=(v*((R-L+1)%ha))%ha; sumv=(sumv+add_v)%ha; } void paint_mul(ll v){ v=v%ha; addv=(addv*v)%ha; mulv=(mulv*v)%ha; sumv=(sumv*v)%ha; } void maintain(){ if(lc!=NULL && rc!=NULL){ sumv=(lc->sumv+rc->sumv)%ha; } } void pushdown(){ if(mulv!=1){ if(lc!=NULL){ lc->paint_mul(mulv); } if(rc!=NULL){ rc->paint_mul(mulv); } mulv=1; } if(addv!=0){ if(lc!=NULL){ lc->paint_add(addv); } if(rc!=NULL){ rc->paint_add(addv); } addv=0; } } }; ll A[maxn]; void build_tree(Node* &o,int L,int R){ if(L==R){ o=new Node(A[L],L); }else{ int M=L+(R-L)/2; Node *lc,*rc; build_tree(lc,L,M); build_tree(rc,M+1,R); o=new Node(lc,rc,L,R); o->maintain(); } } Node *root; int ql,qr; ll v; ll query_sum(Node *o){ int L=o->L,R=o->R; o->pushdown(); if(ql<=L && R<=qr){ return o->sumv; }else{ int M=L+(R-L)/2; ll ans=0; if(ql<=M){ ans=(ans+query_sum(o->lc))%ha; } if(qr>M){ ans=(ans+query_sum(o->rc))%ha; } return ans; } } void update_add(Node *o){ int L=o->L,R=o->R; o->pushdown(); if(ql<=L && R<=qr){ o->paint_add(v); }else{ int M=L+(R-L)/2; if(ql<=M){ update_add(o->lc); } if(qr>M){ update_add(o->rc); } o->maintain(); } } void update_mul(Node *o){ int L=o->L,R=o->R; o->pushdown(); if(ql<=L && R<=qr){ o->paint_mul(v); }else{ int M=L+(R-L)/2; if(ql<=M){ update_mul(o->lc); } if(qr>M){ update_mul(o->rc); } o->maintain(); } } int main(){ register int i; int n,m,op; scanf("%d%lld",&n,&ha); // ha=0x7fffffff; for(i=1;i<=n;i++){ scanf("%lld",&A[i]); } build_tree(root,1,n); scanf("%d",&m); while(m--){ scanf("%d%d%d",&op,&ql,&qr); if(ha==1){ if(op==3){ puts("0"); }else{ scanf("%lld",&v); } continue; } if(op==1){ scanf("%lld",&v); update_mul(root); }else{ if(op==2){ scanf("%lld",&v); update_add(root); }else{ printf("%lld\n",query_sum(root)); } } } return 0; }