[BZOJ1798][Ahoi2009]Seq 维护序列seq

2019-04-13 16:26发布

站内文章 / 模拟电子
14584 0 1624
原题地址 线段树模(mu)板题. AC code: #include typedef long long ll; const int N=100010; ll n,q,m,tot; ll a[N]; struct nod{ ll l,r,sum,tmul,tadd; nod *lc,*rc; }pool[N<<3]; struct Segtree{ nod *root; Segtree(){ build(&root,1,n); } void build(nod **p,ll L,ll R){ *p=&pool[tot++];(*p)->l=L;(*p)->r=R;(*p)->tmul=1; if(L==R){ (*p)->sum=a[L]%q; return ; } ll M=(L+R)>>1; build(&(*p)->lc,L,M); build(&(*p)->rc,M+1,R); (*p)->sum=((*p)->lc->sum+(*p)->rc->sum)%q; } void clear(nod *p){ if(p->l!=p->r){ p->lc->tmul=(p->lc->tmul*p->tmul)%q; p->lc->tadd=(p->lc->tadd*p->tmul)%q; p->rc->tmul=(p->rc->tmul*p->tmul)%q; p->rc->tadd=(p->rc->tadd*p->tmul)%q; p->lc->tadd=(p->lc->tadd+p->tadd)%q; p->rc->tadd=(p->rc->tadd+p->tadd)%q; } p->sum=(p->sum*p->tmul+(p->r-p->l+1)*p->tadd)%q; p->tadd=0;p->tmul=1; } void mul(nod *p,ll L,ll R,ll v){ clear(p); if(p->l==L&&p->r==R){ p->tmul=v; return ; } ll M=(p->l+p->r)>>1; if(R<=M) mul(p->lc,L,R,v); else if(L>M) mul(p->rc,L,R,v); else{ mul(p->lc,L,M,v); mul(p->rc,M+1,R,v); } clear(p->lc);clear(p->rc); p->sum=(p->lc->sum+p->rc->sum)%q; } void add(nod *p,ll L,ll R,ll v){ clear(p); if(p->l==L&&p->r==R){ p->tadd=v; return ; } ll M=(p->l+p->r)>>1; if(R<=M) add(p->lc,L,R,v); else if(L>M) add(p->rc,L,R,v); else{ add(p->lc,L,M,v); add(p->rc,M+1,R,v); } clear(p->lc);clear(p->rc); p->sum=(p->lc->sum+p->rc->sum)%q; } ll query(nod *p,ll L,ll R){ clear(p); if(p->l==L&&p->r==R) return p->sum%q; ll M=(p->l+p->r)>>1; if(R<=M) return query(p->lc,L,R)%q; else if(L>M) return query(p->rc,L,R)%q; else return (query(p->lc,L,M)+query(p->rc,M+1,R))%q; } }; int main(){ scanf("%lld%lld",&n,&q); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); Segtree T; scanf("%lld",&m); for(int i=1;i<=m;i++){ ll t,L,R,v; scanf("%lld%lld%lld",&t,&L,&R); if(t!=3){ scanf("%lld",&v); if(t==1) T.mul(T.root,L,R,v); else T.add(T.root,L,R,v); } else printf("%lld ",T.query(T.root,L,R)); } return 0; }

热门文章