首页 > 代码库 > luogu P3373 【模板】线段树 2
luogu P3373 【模板】线段树 2
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.将某区间每一个数乘上x
3.求出某区间每一个数的和
输入输出格式
输入格式：
第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数乘上k
操作2： 格式：2 x y k 含义：将区间[x,y]内每个数加上k
操作3： 格式：3 x y 含义：输出区间[x,y]内每个数的和对P取模所得的结果
输出格式：
输出包含若干行整数，即为所有操作3的结果。
输入输出样例
输入样例#1：
5 5 381 5 4 2 32 1 4 13 2 51 2 4 22 3 5 53 1 4
输出样例#1：
172
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^）
样例说明：
故输出应为17、2（40 mod 38=2）
需要越来越习惯lazy-tag的使用才行啊
tag1表示乘，tag2表示加
线段树的写法真是各有各的风格 大雾
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 typedef long long ll; 7 8 inline int read(){ 9 char ch; 10 int re=0; 11 bool flag=0; 12 while((ch=getchar())!=‘-‘&&(ch<‘0‘||ch>‘9‘)); 13 ch==‘-‘?flag=1:re=ch-‘0‘; 14 while((ch=getchar())>=‘0‘&&ch<=‘9‘) re=re*10+ch-‘0‘; 15 return flag?-re:re; 16 } 17 18 struct segment{ 19 int l,r; 20 ll sum,tag1,tag2; 21 segment(){ 22 sum=0; 23 tag1=1; 24 tag2=0; 25 } 26 }; 27 28 const int maxn=100001; 29 30 int cnt,n,m; 31 ll mod; 32 segment tre[maxn<<2]; 33 int data[maxn]; 34 35 inline void push_up(int x){ 36 tre[x].sum=(tre[x<<1].sum+tre[x<<1|1].sum)%mod; 37 } 38 39 void build(int x,int l,int r){ 40 tre[x].l=l; tre[x].r=r; 41 if(l==r){ 42 tre[x].sum=data[l]; 43 return; 44 } 45 int mid=(l+r)>>1; 46 build(x<<1,l,mid); build(x<<1|1,mid+1,r); 47 push_up(x); 48 } 49 50 void init(){ 51 n=read(); m=read(); mod=read(); 52 for(int i=1;i<=n;i++) data[i]=read(); 53 build(1,1,n); 54 } 55 56 inline void push_down(int x){ 57 int lson=x<<1,rson=lson|1; 58 59 if(tre[x].tag1!=1){ 60 tre[lson].tag1=(tre[lson].tag1*tre[x].tag1)%mod; 61 tre[rson].tag1=(tre[rson].tag1*tre[x].tag1)%mod; 62 tre[lson].tag2=(tre[lson].tag2*tre[x].tag1)%mod; 63 tre[rson].tag2=(tre[rson].tag2*tre[x].tag1)%mod; 64 tre[lson].sum=(tre[lson].sum*tre[x].tag1)%mod; 65 tre[rson].sum=(tre[rson].sum*tre[x].tag1)%mod; 66 tre[x].tag1=1; 67 } 68 69 if(tre[x].tag2){ 70 tre[lson].tag2=(tre[lson].tag2+tre[x].tag2)%mod; 71 tre[lson].sum=(tre[lson].sum+tre[x].tag2*(tre[lson].r-tre[lson].l+1))%mod; 72 tre[rson].tag2=(tre[rson].tag2+tre[x].tag2)%mod; 73 tre[rson].sum=(tre[rson].sum+tre[x].tag2*(tre[rson].r-tre[rson].l+1))%mod; 74 tre[x].tag2=0; 75 } 76 } 77 78 void update_add(int x,int L,int R,int c){ 79 if(L<=tre[x].l&&tre[x].r<=R){ 80 tre[x].tag2=(tre[x].tag2+c)%mod; 81 tre[x].sum=(tre[x].sum+c*(tre[x].r-tre[x].l+1))%mod; 82 return; 83 } 84 85 int mid=(tre[x].l+tre[x].r)>>1; 86 if(tre[x].tag1!=1||tre[x].tag2) push_down(x); 87 if(R<=mid) update_add(x<<1,L,R,c); 88 else if(L>mid) update_add(x<<1|1,L,R,c); 89 else{ update_add(x<<1,L,mid,c); update_add(x<<1|1,mid+1,R,c); } 90 push_up(x); 91 } 92 93 void update_mul(int x,int L,int R,int c){ 94 if(L<=tre[x].l&&tre[x].r<=R){ 95 tre[x].tag1=(tre[x].tag1*c)%mod; 96 tre[x].tag2=(tre[x].tag2*c)%mod; 97 tre[x].sum=(tre[x].sum*c)%mod; 98 return; 99 }100 101 int mid=(tre[x].l+tre[x].r)>>1;102 if(tre[x].tag1!=1||tre[x].tag2) push_down(x);103 if(R<=mid) update_mul(x<<1,L,R,c);104 else if(L>mid) update_mul(x<<1|1,L,R,c);105 else{ update_mul(x<<1,L,mid,c); update_mul(x<<1|1,mid+1,R,c); }106 push_up(x);107 }108 109 ll query_sum(int x,int L,int R){110 if(L<=tre[x].l&&tre[x].r<=R){111 return tre[x].sum;112 }113 if(tre[x].tag1!=1||tre[x].tag2) push_down(x);114 int mid=(tre[x].l+tre[x].r)>>1;115 if(R<=mid) return query_sum(x<<1,L,R);116 if(L>mid) return query_sum(x<<1|1,L,R);117 return (query_sum(x<<1,L,mid)+query_sum(x<<1|1,mid+1,R))%mod;118 }119 120 void solve(){121 int opt,L,R,c;122 for(int i=0;i<m;i++){123 opt=read();124 switch(opt){125 case 1:{126 L=read(); R=read(); c=read();127 update_mul(1,L,R,c);128 break;129 }130 case 2:{131 L=read(); R=read(); c=read();132 update_add(1,L,R,c);133 break;134 }135 case 3:{136 L=read(); R=read();137 printf("%lld\n",query_sum(1,L,R));138 break;139 }140 }141 }142 }143 144 int main(){145 //freopen("temp.in","r",stdin);146 init();147 solve();148 return 0;149 }
她的话不多但笑起来是那么平静优雅
她柔弱的眼神里装的是什么 是思念的忧伤
luogu P3373 【模板】线段树 2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。