P3373【模板】线段树 2
1.将某区间每一个数乘上x
2.将某区间每一个数加上x
3.求出某区间每一个数的和
#include<bits/stdc++.h> using namespace std; #define MAX 100005 #define ll long long #define inf 0x3f3f3f ll num[MAX]; int n,m; ll p; struct node{ ll val; ll add; ll mul; int l,r; }segtree[(MAX<<2)+5]; void build(int root,int nl,int nr){ segtree[root].add=0; segtree[root].mul=1; if(nl==nr){ segtree[root].val=num[nl]; return ; } int mid=nr+nl>>1; build(root<<1,nl,mid); build(root<<1|1,mid+1,nr); segtree[root].val=segtree[root<<1].val+segtree[root<<1|1].val; segtree[root].val%=p; } void pushdown(int root,int nl,int nr){ int mid = nr+nl>>1; segtree[root<<1].val=segtree[root<<1].val*segtree[root].mul+segtree[root].add*(mid-nl+1); segtree[root<<1|1].val=segtree[root<<1|1].val*segtree[root].mul+segtree[root].add*(nr-mid); segtree[root<<1].add=segtree[root<<1].add*segtree[root].mul+segtree[root].add; segtree[root<<1|1].add=segtree[root<<1|1].add*segtree[root].mul+segtree[root].add; segtree[root<<1].mul*=segtree[root].mul; segtree[root<<1|1].mul*=segtree[root].mul; segtree[root].add=0; segtree[root].mul=1; segtree[root<<1].val%=p; segtree[root<<1|1].val%=p; segtree[root<<1].add%=p; segtree[root<<1|1].add%=p; segtree[root<<1].mul%=p; segtree[root<<1|1].mul%=p; } ll query(int root,int nl,int nr,int ql,int qr){ if(nl>qr||nr<ql){ return 0; } if(nl>=ql&&nr<=qr){ return segtree[root].val; } pushdown(root,nl,nr); int mid=nl+nr>>1; return (query(root<<1,nl,mid,ql,qr)%p+query(root<<1|1,mid+1,nr,ql,qr)%p)%p; } void update(int root,int nl,int nr,int ql,int qr,int add){ if(nl>qr||nr<ql){ return ; } if(nl>=ql&&nr<=qr){ segtree[root].val+=(nr-nl+1)*add; segtree[root].val%=p; segtree[root].add+=add; segtree[root].add%=p; return ; } pushdown(root,nl,nr); if(nl==nr){ segtree[root].val+=add; segtree[root].val%=p; return ; } int mid=nl+nr>>1; update(root<<1,nl,mid,ql,qr,add); update(root<<1|1,mid+1,nr,ql,qr,add); segtree[root].val=segtree[root<<1].val+segtree[root<<1|1].val; segtree[root].val%=p; } void update2(int root,int nl,int nr,int ql,int qr,int mul){ if(nl>qr||nr<ql){ return ; } if(nl>=ql&&nr<=qr){ segtree[root].val*=mul; segtree[root].add*=mul; segtree[root].mul*=mul; segtree[root].val%=p; segtree[root].add%=p; segtree[root].mul%=p; return ; } pushdown(root,nl,nr); if(nl==nr){ segtree[root].val*=mul; segtree[root].val%=p; return ; } int mid=nl+nr>>1; update2(root<<1,nl,mid,ql,qr,mul); update2(root<<1|1,mid+1,nr,ql,qr,mul); segtree[root].val=segtree[root<<1].val+segtree[root<<1|1].val; segtree[root].val%=p; } int main(){ scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++){ scanf("%lld",&num[i]); } build(1,1,n); for(int i=1;i<=m;i++){ int a; scanf("%d",&a); if(a==1){ int b,c,d; scanf("%d%d%d",&b,&c,&d); update2(1,1,n,b,c,d); } else if(a==2){ int b,c,d; scanf("%d%d%d",&b,&c,&d); update(1,1,n,b,c,d); } else if(a==3){ int b,c; scanf("%d%d",&b,&c); printf("%lld\n",query(1,1,n,b,c)); } } return 0; }
