首页 > 代码库 > [AHOI2009]维护序列

[AHOI2009]维护序列

OJ题号:洛谷2023、BZOJ1798

思路:

参见[洛谷3373]【模板】线段树 2

  1 #include<cstdio>  2 #include<cctype>  3 #include<cstring>  4 #include<cstdlib>  5 #include<algorithm>  6 using namespace std;  7 #define ll long long  8 #define maxn 100001  9 #define root 1 10 #define _left <<1 11 #define _right <<1|1 12 int n,m; 13 ll mod; 14 inline int getint() { 15     char ch; 16     while(!isdigit(ch=getchar())); 17     int x=ch^0; 18     while(isdigit(ch=getchar())) x=((x+(x<<2))<<1)+(ch^0); 19     return x; 20 } 21 inline ll getll() { 22     char ch; 23     while(!isdigit(ch=getchar())); 24     ll x=ch^0; 25     while(isdigit(ch=getchar())) x=((x+(x<<2))<<1)+(ch^0); 26     return x; 27 } 28 struct SegmentTree { 29     ll val[maxn<<2],add[maxn<<2],mul[maxn<<2]; 30     void push_up(const int p) { 31         val[p]=(val[p _left]+val[p _right])%mod; 32     } 33     void build(const int p,const int b,const int e) { 34         mul[p]=1; 35         add[p]=0; 36         if(b==e) { 37             val[p]=getll()%mod; 38             return; 39         } 40         int mid=(b+e)>>1; 41         build(p _left,b,mid); 42         build(p _right,mid+1,e); 43         push_up(p); 44     } 45     int length(const int b,const int e) { 46         return e-b+1; 47     } 48     void push_down(const int p,const int b,const int e) { 49         if(mul[p]!=1) { 50             val[p _left]=val[p _left]*mul[p]%mod; 51             val[p _right]=val[p _right]*mul[p]%mod; 52             mul[p _left]=mul[p _left]*mul[p]%mod; 53             mul[p _right]=mul[p _right]*mul[p]%mod; 54             add[p _left]=add[p _left]*mul[p]%mod; 55             add[p _right]=add[p _right]*mul[p]%mod; 56             mul[p]=1;  57         } 58         if(add[p]) { 59             int mid=(b+e)>>1; 60             val[p _left]=(val[p _left]+add[p]*length(b,mid))%mod; 61             val[p _right]=(val[p _right]+add[p]*length(mid+1,e))%mod; 62             add[p _left]=(add[p _left]+add[p])%mod; 63             add[p _right]=(add[p _right]+add[p])%mod; 64             add[p]=0; 65         } 66     } 67     void modify_mul(const int p,const int b,const int e,const int l,const int r,const ll x) { 68         if((b==l)&&(e==r)) { 69             val[p]=val[p]*x%mod; 70             mul[p]=mul[p]*x%mod; 71             add[p]=add[p]*x%mod; 72             return; 73         } 74         push_down(p,b,e); 75         int mid=(b+e)>>1; 76         if(l<=mid) modify_mul(p _left,b,mid,l,min(mid,r),x); 77         if(r>mid) modify_mul(p _right,mid+1,e,max(mid+1,l),r,x); 78         push_up(p); 79     } 80     void modify_add(const int p,const int b,const int e,const int l,const int r,const ll x) { 81         if((b==l)&&(e==r)) { 82             val[p]=(val[p]+x*length(b,e))%mod; 83             add[p]=(add[p]+x)%mod; 84             return; 85         } 86         push_down(p,b,e); 87         int mid=(b+e)>>1; 88         if(l<=mid) modify_add(p _left,b,mid,l,min(mid,r),x); 89         if(r>mid) modify_add(p _right,mid+1,e,max(mid+1,l),r,x); 90         push_up(p); 91     } 92     ll query(const int p,const int b,const int e,const int l,const int r) { 93         if((b==l)&&(e==r)) { 94             return val[p]; 95         } 96         int mid=(b+e)>>1; 97         ll ans=0; 98         push_down(p,b,e); 99         if(l<=mid) ans=(ans+query(p _left,b,mid,l,min(mid,r)))%mod;100         if(r>mid) ans=(ans+query(p _right,mid+1,e,max(mid+1,l),r))%mod;101         return ans;102     }103 };104 SegmentTree tree;105 int main() {106     n=getint();107     mod=getll();108     tree.build(root,1,n);109     m=getint();110     while(m--) {111         int op=getint(),x=getint(),y=getint();112         if(op==1) {113             ll k=getll()%mod;114             tree.modify_mul(root,1,n,x,y,k);115             continue;116         }117         if(op==2) {118             ll k=getll()%mod;119             tree.modify_add(root,1,n,x,y,k);120             continue;121         }122         printf("%lld\n",tree.query(root,1,n,x,y));123     }124     return 0;125 }

 

[AHOI2009]维护序列