1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
| #include<bits/stdc++.h> using namespace std; template<typename __Type_of_scan> void scan(__Type_of_scan &x) { __Type_of_scan f=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=f; } template<typename __Type_of_print> void print(__Type_of_print x) { if(x<0){putchar('-');x=-x;} if(x>9)print(x/10); putchar(x%10+'0'); } int n,m; long long p; long long a[100005],ans[400005],add[400005],mul[400005]; int ls(int x){return x<<1;} int rs(int x){return x<<1|1;} void push_up(int x){ans[x]=(ans[ls(x)]+ans[rs(x)])%p;} void build(int x,int l,int r) { add[x]=0;mul[x]=1; if(l==r) { ans[x]=a[l]; return ; } int mid=(l+r)>>1; build(ls(x),l,mid); build(rs(x),mid+1,r); push_up(x); } void push_down(int x,int l,int r) { int mid=(l+r)>>1; mul[ls(x)]=(mul[ls(x)]*mul[x])%p; mul[rs(x)]=(mul[rs(x)]*mul[x])%p; add[ls(x)]=(add[ls(x)]*mul[x])%p; add[rs(x)]=(add[rs(x)]*mul[x])%p; ans[ls(x)]=(ans[ls(x)]*mul[x])%p; ans[rs(x)]=(ans[rs(x)]*mul[x])%p; mul[x]=1; add[ls(x)]=(add[ls(x)]+add[x])%p; add[rs(x)]=(add[rs(x)]+add[x])%p; ans[ls(x)]=(ans[ls(x)]+add[x]*(mid-l+1))%p; ans[rs(x)]=(ans[rs(x)]+add[x]*(r-mid))%p; add[x]=0; } void addup(int nl,int nr,int l,int r,int x,long long k) { if(nl<=l&&r<=nr) { ans[x]=(ans[x]+k*(r-l+1))%p; add[x]=(add[x]+k)%p; return ; } push_down(x,l,r); int mid=(l+r)>>1; if(nl<=mid)addup(nl,nr,l,mid,ls(x),k); if(mid+1<=nr)addup(nl,nr,mid+1,r,rs(x),k); push_up(x); } void mulup(int nl,int nr,int l,int r,int x,long long k) { if(nl<=l&&r<=nr) { ans[x]=(ans[x]*k)%p; mul[x]=(mul[x]*k)%p; add[x]=(add[x]*k)%p; return ; } push_down(x,l,r); int mid=(l+r)>>1; if(nl<=mid)mulup(nl,nr,l,mid,ls(x),k); if(mid+1<=nr)mulup(nl,nr,mid+1,r,rs(x),k); push_up(x); } long long query(int ql,int qr,int l,int r,int x) { long long res=0; if(ql<=l&&r<=qr)return ans[x]%p; int mid=(l+r)>>1; push_down(x,l,r); if(ql<=mid)res+=query(ql,qr,l,mid,ls(x)); if(mid+1<=qr)res+=query(ql,qr,mid+1,r,rs(x)); return res%p; } int main() { scan(n),scan(m),scan(p); for(int i=1;i<=n;i++) scan(a[i]); build(1,1,n); for(int i=1,opt,x,y;i<=m;i++) { scan(opt),scan(x),scan(y); if(opt==1) { long long k; scan(k); mulup(x,y,1,n,1,k); } if(opt==2) { long long k; scan(k); addup(x,y,1,n,1,k); } if(opt==3) { print(query(x,y,1,n,1)),putchar('\n'); } } }
|