双倍的快乐 P2023 [AHOI2009]维护序列 P3373 【模板】线段树 2
看学长的模板然后改了一下
要注意每次询问时pushdown 然后就是这道题要注意开longlong 从学长那里学来的*1ll好像对我并没有什么用QAQ
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 #include<cmath> 7 #include<vector> 8 #include<stack> 9 #include<map> 10 #include<set> 11 #define Run(i,l,r) for(int i=l;i<=r;i++) 12 #define Don(i,l,r) for(int i=l;i>=r;i--) 13 #define ll long long 14 #define ld long double 15 #define inf 0x3f3f3f3f 16 #define ls k<<1 17 #define rs (k<<1|1) 18 #define rg register 19 using namespace std; 20 const int N=100010; 21 int n,m,sum[N<<2],lz1[N<<2],lz2[N<<2],mod; 22 char gc(){ 23 static char*p1,*p2,s[1000000]; 24 if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); 25 return(p1==p2)?EOF:*p1++; 26 } 27 int rd(){ 28 int x=0,f=1;char c=gc(); 29 while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();} 30 while(c>='0'&&c<='9'){x=x*10+c-'0',c=gc();} 31 return x*f; 32 } 33 void pushup(int k){ 34 sum[k]=(sum[ls]+sum[rs]); 35 if(sum[k]>=mod)sum[k]-=mod; 36 } 37 void mfy1(int k,int l,int r,int v){ 38 sum[k]=1ll*sum[k]*v%mod; 39 lz1[k]=1ll*lz1[k]*v%mod; 40 lz2[k]=1ll*lz2[k]*v%mod; 41 } 42 void mfy2(int k,int l,int r,int v){ 43 sum[k]=(sum[k]+1ll*(r-l+1)*v%mod)%mod; 44 lz2[k]=(lz2[k]+v)%mod; 45 } 46 void pushdown(int k,int l,int r){ 47 int mid=(l+r)>>1; 48 if(lz1[k]!=1){ 49 mfy1(ls,l,mid,lz1[k]); 50 mfy1(rs,mid+1,r,lz1[k]); 51 lz1[k]=1; 52 } 53 if(lz2[k]){ 54 mfy2(ls,l,mid,lz2[k]); 55 mfy2(rs,mid+1,r,lz2[k]); 56 lz2[k]=0; 57 } 58 } 59 void build(int k,int l,int r){ 60 lz1[k]=1; lz2[k]=0; 61 if(l==r){sum[k]=rd();return;} 62 int mid=(l+r)>>1; 63 build(ls,l,mid); 64 build(rs,mid+1,r); 65 pushup(k); 66 } 67 void update1(int k,int l,int r,int x,int y,int v){ 68 if(l==x&&r==y)mfy1(k,l,r,v); 69 else{ 70 pushdown(k,l,r); 71 int mid=(l+r)>>1; 72 if(y<=mid)update1(ls,l,mid,x,y,v); 73 else if(x>mid)update1(rs,mid+1,r,x,y,v); 74 else update1(ls,l,mid,x,mid,v),update1(rs,mid+1,r,mid+1,y,v); 75 pushup(k); 76 } 77 } 78 void update2(int k,int l,int r,int x,int y,int v){ 79 if(l==x&&r==y)mfy2(k,l,r,v); 80 else{ 81 pushdown(k,l,r); 82 int mid=(l+r)>>1; 83 if(y<=mid)update2(ls,l,mid,x,y,v); 84 else if(x>mid)update2(rs,mid+1,r,x,y,v); 85 else update2(ls,l,mid,x,mid,v),update2(rs,mid+1,r,mid+1,y,v); 86 pushup(k); 87 } 88 } 89 int query(int k,int l,int r,int x,int y){ 90 if(l==x&&r==y)return sum[k]; 91 else{ 92 pushdown(k,l,r); 93 int mid=(l+r)>>1; 94 if(y<=mid)return query(ls,l,mid,x,y); 95 else if(x>mid)return query(rs,mid+1,r,x,y); 96 else return (query(ls,l,mid,x,mid) + query(rs,mid+1,r,mid+1,y))%mod; 97 } 98 } 99 int main(){ 100 freopen("P3373.in","r",stdin); 101 freopen("P3373.out","w",stdout); 102 n=rd(); m=rd(); mod=rd(); 103 build(1,1,n); 104 for(rg int i=1,op,x,y,v;i<=m;i++){ 105 op=rd(); x=rd(); y=rd(); 106 if(op!=3)v=rd(); 107 if(op==1)update1(1,1,n,x,y,v); 108 else if(op==2)update2(1,1,n,x,y,v); 109 else printf("%d ",query(1,1,n,x,y)); 110 } 111 return 0; 112 }//by tkys_Austin; 113 114 115 116 117 //分区间的时候注意一下x和y，一不小心就写错； 118 //我，竟然只开了两倍空间。。。。。 119 //20181109 120
区间加和区间乘
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<cmath> 6 #include<stack> 7 #include<algorithm> 8 using namespace std; 9 #define ll long long 10 #define rg register 11 #define ls o<<1 12 #define rs o<<1|1 13 const int N=100000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827; 14 int n,m,p,a[N]; 15 ll sum[N<<2],add[N<<2],mul[N<<2]; 16 template <class t>void rd(t &x) 17 { 18 x=0;int w=0;char ch=0; 19 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 20 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 21 x=w?-x:x; 22 } 23 24 void pushup(int o){ 25 sum[o]=(sum[ls]+sum[rs])%p; 26 } 27 void updatenode1(int o,int l,int r,int k){ 28 sum[o]=1ll*sum[o]*k%p; 29 add[o]=1ll*add[o]*k%p; 30 mul[o]=1ll*mul[o]*k%p; 31 } 32 void updatenode2(int o,int l,int r,int k){ 33 sum[o]=(sum[o]+1ll*(r-l+1)*k%p)%p; 34 add[o]=(add[o]+k)%p; 35 } 36 37 void pushdown(int o,int l,int r){ 38 int mid=(l+r)>>1; 39 /* sum[ls]=(1ll*sum[ls]*mul[o]+1ll*add[o]*(mid-l+1))%p; 40 sum[rs]=(1ll*sum[rs]*mul[o]+1ll*add[o]*(r-mid))%p; 41 mul[ls]=(1ll*mul[ls]*mul[o])%p; 42 mul[rs]=(1ll*mul[rs]*mul[o])%p; 43 add[ls]=(1ll*add[ls]*mul[o]+add[o])%p; 44 add[rs]=(1ll*add[rs]*mul[o]+add[o])%p; 45 add[o]=0,mul[o]=1;*/ 46 if(mul[o]!=1){ 47 updatenode1(ls,l,mid,mul[o]); 48 updatenode1(rs,mid+1,r,mul[o]); 49 mul[o]=1; 50 } 51 if(add[o]){ 52 updatenode2(ls,l,mid,add[o]); 53 updatenode2(rs,mid+1,r,add[o]); 54 add[o]=0; 55 } 56 } 57 58 void update1(int o,int l,int r,int x,int y,int k){ 59 if(r<x||y<l) return; 60 if(x<=l&&r<=y) {updatenode1(o,l,r,k);return;} 61 pushdown(o,l,r); 62 int mid=(l+r)>>1; 63 update1(ls,l,mid,x,y,k); 64 update1(rs,mid+1,r,x,y,k); 65 pushup(o); 66 return; 67 } 68 void update2(int o,int l,int r,int x,int y,int k){ 69 if(r<x||y<l) return; 70 if(x<=l&&r<=y) {updatenode2(o,l,r,k);return;} 71 pushdown(o,l,r); 72 int mid=(l+r)>>1; 73 update2(ls,l,mid,x,y,k); 74 update2(rs,mid+1,r,x,y,k); 75 pushup(o); 76 return; 77 } 78 79 void buildtree(int o,int l,int r){ 80 add[o]=0,mul[o]=1; 81 if(l==r) {sum[o]=a[l];return;} 82 int mid=(l+r)>>1; 83 buildtree(ls,l,mid); 84 buildtree(rs,mid+1,r); 85 pushup(o); 86 } 87 int query(int o,int l,int r,int x,int y){ 88 int ans=0; 89 if(r<x||y<l) return 0; 90 if(x<=l&&r<=y) return sum[o]; 91 pushdown(o,l,r); 92 int mid=(l+r)>>1; 93 ans=(ans+query(ls,l,mid,x,y))%p; 94 ans=(ans+query(rs,mid+1,r,x,y))%p; 95 return ans; 96 } 97 98 int main(){ 99 rd(n),rd(m),rd(p); 100 for(rg int i=1;i<=n;++i) rd(a[i]); 101 buildtree(1,1,n); 102 for(rg int i=1,op,x,y,k;i<=m;++i){ 103 rd(op),rd(x),rd(y); 104 if(op!=3) rd(k); 105 if(op==1) update1(1,1,n,x,y,k); 106 else if(op==2) update2(1,1,n,x,y,k); 107 else printf("%d ",query(1,1,n,x,y)); 108 } 109 return 0; 110 } 111