洛谷P2023 [AHOI2009]维护序列线段树

洛谷P2023 [AHOI2009]维护序列

线段树带乘法标记和加法标记
处理两个标记时记得要两个标记之间互不影响，
如果有影响，则要改变一下

我们一律先处理乘法标记在处理加法标记
如果已经有了加法标记又来了一个乘法标记
那么加法标记也要乘否则就不能做到强制先后了
这样就能保证标记之间互不影响

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream> 
  8 #include <iomanip>
  9 #define ll long long  
 10 using namespace std ; 
 11 
 12 const int maxn = 100011 ; 
 13 
 14 struct node{
 15     int l,r ;
 16     ll sum,ADD,MUL ; 
 17 }tree[maxn*4];
 18 int n,Q ; 
 19 ll ans,v,mod ; 
 20 int a[maxn] ; 
 21 
 22 inline ll read() 
 23 {
 24     char ch = getchar() ; 
 25     ll  x=0,f=1 ; 
 26     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 
 27     while(ch>='0'&&ch<='9') { x = x*10+ch-48 ; ch = getchar() ; } 
 28     return x * f ; 
 29 }
 30 
 31 inline void write(ll x) 
 32 {
 33     if(x<0) x = -x,putchar('-') ; 
 34     if(x>9) write(x/10) ; 
 35     putchar(x % 10 + 48 ) ;    
 36 }  
 37 
 38 inline void writeln(ll x )  { write(x) ; putchar('
') ; }  
 39 inline void pushup(int root) 
 40 {
 41     tree[root].sum = ( tree[root<<1].sum + tree[root<<1|1].sum ) %mod ; 
 42 }
 43 
 44 inline void build(int root,int l,int r) 
 45 {
 46     tree[root].l = l ;  tree[root].r = r ;  
 47     tree[root].MUL = 1 ;tree[root].ADD = 0 ; 
 48     if(l==r) 
 49     {
 50         tree[root].sum = a[ l ] ;
 51         return ;  
 52     }
 53     int mid = (l+r) /2 ; 
 54     build(root<<1,l,mid) ; 
 55     build(root<<1|1,mid+1,r) ; 
 56     pushup(root) ; 
 57 }
 58 
 59 inline void pushdown(int root) 
 60 {
 61     if(tree[root].MUL==1&&tree[root].ADD==0) return ; 
 62     tree[root<<1].ADD =  ( tree[root<<1].ADD * tree[root].MUL +tree[root].ADD ) %mod ; 
 63     tree[root<<1|1].ADD = (tree[root<<1|1].ADD*tree[root].MUL +tree[root].ADD ) %mod ; 
 64     
 65     tree[root<<1].MUL = tree[root<<1].MUL * tree[root].MUL % mod ; 
 66     tree[root<<1|1].MUL = tree[root<<1|1].MUL*tree[root].MUL % mod ; 
 67     
 68     tree[root<<1].sum=( tree[root<<1].sum * tree[root].MUL + tree[root].ADD *(tree[root<<1].r-tree[root<<1].l+1)  ) % mod;
 69     tree[root<<1|1].sum=( tree[root<<1|1].sum*tree[root].MUL + tree[root].ADD *(tree[root<<1|1].r-tree[root<<1|1].l+1)  ) % mod;
 70     tree[root].MUL = 1 ; 
 71     tree[root].ADD = 0 ;  
 72 }
 73 
 74 inline void updata(int root,int l,int r,ll mul,ll add) 
 75 {
 76     if(tree[root].l==l&&tree[root].r==r) 
 77     {
 78         tree[root].ADD = (  tree[root].ADD * mul + add )  % mod ; 
 79         tree[root].MUL = tree[root].MUL * mul % mod ; 
 80         tree[root].sum = ( tree[root].sum*mul  + (tree[root].r-tree[root].l+1) * add ) %mod ;  
 81         return ; 
 82     }
 83     pushdown(root) ; 
 84     int mid = (tree[root].l + tree[root].r) /2 ; 
 85     if( r<=mid ) updata(root<<1,l,r,mul,add) ; 
 86     else if( l>mid )  updata(root<<1|1,l,r,mul,add) ; 
 87     else 
 88     {
 89         updata(root<<1,l,mid,mul,add) ; 
 90         updata(root<<1|1,mid+1,r,mul,add) ; 
 91     }
 92     pushup(root) ; 
 93 }
 94 
 95 inline ll query(int root,int l,int r) 
 96 {
 97     if(tree[root].l==l&&tree[root].r==r) 
 98         return tree[root].sum ; 
 99     pushdown(root) ; 
100     
101     int mid = (tree[root].l + tree[root].r) /2 ; 
102     if( r<=mid ) return query(root<<1,l,r)  ; 
103     if( l>mid )  return query(root<<1|1,l,r) ; 
104     ll ans = 0 ; 
105     ans = (ans+query(root<<1,l,mid)) %mod ; 
106     ans = (ans+query(root<<1|1,mid+1,r)) %mod ; 
107     return ans ;     
108 }
109 
110 int main() 
111 {
112     n = read() ; mod = read() ; 
113     for(int i=1;i<=n;i++) 
114         a[ i ] = read(),a[ i ] %=mod ; 
115     build(1,1,n) ; 
116     Q = read() ; 
117     int type,l,r ; 
118     for(int i=1;i<=Q;i++) 
119     {
120         type = read() ; l = read() ;  r = read() ; 
121         if(type==1) 
122         {
123             v = read() ;  v%=mod ; 
124             updata(1,l,r,v,0) ;  
125         }
126         if(type==2) 
127         {
128             v = read() ; v%=mod ; 
129             updata(1,l,r,1,v) ; 
130         } 
131         if(type==3) 
132         {
133             ans = query(1,l,r) %mod ; 
134             writeln( ans ) ; 
135         }
136     } 
137     
138      return 0 ; 
139 }

洛谷P2023 [AHOI2009]维护序列 线段树

洛谷P2023 [AHOI2009]维护序列线段树