题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1798
题意：维护序列，支持区间加，区间乘，区间求和
坑了好久的大水题 T.T，注意先传乘法标记即可。
然而一直调不对 T.T
|
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 |
#include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iomanip> #include <iostream> #include <algorithm> #define ll long long #define N 200010 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,p,m,opt; ll sum[N<<2],add[N<<2],mul[N<<2]; void pushdown(ll x,ll l,ll r) { ll mid=(l+r)>>1; if(mul[x]!=1||add[x]!=0) { mul[x<<1]=(mul[x<<1]*mul[x])%p; mul[x<<1|1]=(mul[x<<1|1]*mul[x])%p; add[x<<1]=(mul[x]*add[x<<1]+add[x])%p; add[x<<1|1]=(mul[x]*add[x<<1|1]+add[x])%p; sum[x<<1]=(sum[x<<1]*mul[x]+(mid-l+1)*add[x])%p; sum[x<<1|1]=(sum[x<<1|1]*mul[x]+(r-mid)*add[x])%p; mul[x]=1,add[x]=0; } } void pushup(ll x) {sum[x]=(sum[x<<1]+sum[x<<1|1])%p;} void modify_add(ll x,ll l,ll r,ll L,ll R,ll val) { if(l>=L&&r<=R) { (sum[x]+=(r-l+1)*val)%=p; (add[x]+=val)%=p; return ; } pushdown(x,l,r); ll mid=(l+r)>>1; if(L<=mid)modify_add(x<<1,l,mid,L,R,val); if(R>mid) modify_add(x<<1|1,mid+1,r,L,R,val); pushup(x); } void modify_mul(ll x,ll l,ll r,ll L,ll R,ll val) { if(l>=L&&r<=R) { (sum[x]*=val)%=p; (add[x]*=val)%=p; (mul[x]*=val)%=p; return ; } pushdown(x,l,r); ll mid=(l+r)>>1; if(L<=mid)modify_mul(x<<1,l,mid,L,R,val); if(R>mid) modify_mul(x<<1|1,mid+1,r,L,R,val); pushup(x); } ll query(ll x,ll l,ll r,ll L,ll R) { if(l>=L&&r<=R) {return sum[x];} pushdown(x,l,r); ll mid=(l+r)>>1,tmp=0; if(L<=mid)(tmp+=query(x<<1,l,mid,L,R))%=p; if(R>mid) (tmp+=query(x<<1|1,mid+1,r,L,R))%=p; pushup(x); return tmp; } void build(int x,int l,int r) { mul[x]=1,sum[x]=0; if(l==r) { sum[x]=read(); return ; } int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); pushup(x); } int main() { n=read(),p=read(); build(1,1,n); m=read(); for(int i=1;i<=m;i++) { opt=read(); ll l=read(),r=read(),c=0; if(opt!=3)c=read(); if(opt==1)modify_mul(1,1,n,l,r,c); if(opt==2)modify_add(1,1,n,l,r,c); if(opt==3)printf("%lld\n",query(1,1,n,l,r)%p); } } |
Comments | 1 条评论
博主，我要帐号