首页 > 代码库 > 【模板】线段树 2
【模板】线段树 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 38 1 5 4 2 3 2 1 4 1 3 2 5 1 2 4 2 2 3 5 5 3 1 4
输出样例#1：
17 2
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^）
样例说明：
故输出应为17、2（40 mod 38=2）
思路：
问题主要是没法分断是先乘还是先加，我同学说可以能个栈存一下，线段树里的栈。。。恕我无能。
一般的解决方法是把乘法变成加法。
（s+flag）*lazy=s*lazy+flag*lazy。
注意：
数据规模，不仅要开long long，还要时常取mod。
（根据评论中的话，好像不开long long也行，但即使数据是int范围内的，因为有乘法操作，可能会动不动就到了long long范围内。noip时，Linux格式化输入输出lld。）
代码实现：
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 #define LL long long 5 LL n,m,mod,a,b,c,d; 6 struct nate{LL l,r,s,flag,lazy;}t[800000];//flag 7 void heritage(LL k){//标记传递。 8 if(t[k].lazy==1&&t[k].flag==0) return; 9 if(t[k].l==t[k].r){t[k].flag=0;t[k].lazy=1;return;} 10 LL lson=k*2,rson=k*2+1; 11 t[lson].s=((t[lson].s*t[k].lazy)%mod+(t[k].flag*(t[lson].r-t[lson].l+1))%mod)%mod; 12 t[lson].flag=((t[lson].flag*t[k].lazy)%mod+t[k].flag)%mod; 13 t[lson].lazy=(t[lson].lazy*t[k].lazy)%mod; 14 t[rson].s=((t[rson].s*t[k].lazy)%mod+(t[k].flag*(t[rson].r-t[rson].l+1))%mod)%mod; 15 t[rson].flag=((t[rson].flag*t[k].lazy)%mod+t[k].flag)%mod; 16 t[rson].lazy=(t[rson].lazy*t[k].lazy)%mod; 17 t[k].flag=0;t[k].lazy=1; 18 } 19 void make_tree(LL k,LL l,LL r){//建树。一般建法。 20 LL lson=k*2,rson=k*2+1; 21 t[k].l=l;t[k].r=r;t[k].lazy=1; 22 if(l==r){scanf("%lld",&t[k].s);t[k].s%=mod;return;} 23 LL mid=(l+r)/2; 24 make_tree(lson,l,mid); 25 make_tree(rson,mid+1,r); 26 t[k].s=(t[lson].s+t[rson].s)%mod; 27 } 28 void interval_add(LL k,LL l,LL r,LL v){//加法更值。 29 LL lson=k*2,rson=k*2+1; 30 heritage(k); 31 if(t[k].l==l&&t[k].r==r){ 32 t[k].flag=v; 33 t[k].s=(t[k].s+((t[k].r-t[k].l+1)*v)%mod)%mod; 34 return; 35 } 36 LL mid=(t[k].l+t[k].r)/2; 37 if(l<=mid) interval_add(lson,l,min(r,mid),v); 38 if(r>mid) interval_add(rson,max(l,mid+1),r,v); 39 t[k].s=(t[lson].s+t[rson].s)%mod; 40 } 41 void interval_ride(LL k,LL l,LL r,LL v){//乘法更值。 42 LL lson=k*2,rson=k*2+1; 43 heritage(k); 44 if(t[k].l==l&&t[k].r==r){ 45 t[k].lazy=v; 46 t[k].s=(t[k].s*v)%mod; 47 return; 48 } 49 LL mid=(t[k].l+t[k].r)/2; 50 if(l<=mid) interval_ride(lson,l,min(r,mid),v); 51 if(r>mid) interval_ride(rson,max(l,mid+1),r,v); 52 t[k].s=(t[lson].s+t[rson].s)%mod; 53 } 54 LL interval_query(LL k,LL l,LL r){//区间查询。 55 int lson=k*2,rson=k*2+1; 56 heritage(k); 57 if(t[k].l==l&&t[k].r==r) return t[k].s; 58 LL mid=(t[k].l+t[k].r)/2,ans=0; 59 if(l<=mid) ans+=interval_query(lson,l,min(r,mid)); 60 if(r>mid) ans+=interval_query(rson,max(l,mid+1),r); 61 return ans%mod; 62 } 63 int main(){ 64 scanf("%lld%lld%lld",&n,&m,&mod); 65 make_tree(1,1,n); 66 for(int i=1;i<=m;i++){ 67 scanf("%lld",&a); 68 if(a==1){ 69 scanf("%lld%lld%lld",&b,&c,&d); 70 interval_ride(1,b,c,d%mod); 71 } 72 if(a==2){ 73 scanf("%lld%lld%lld",&b,&c,&d); 74 interval_add(1,b,c,d%mod); 75 } 76 if(a==3){ 77 scanf("%lld%lld",&b,&c); 78 printf("%lld\n",interval_query(1,b,c)); 79 } 80 } 81 return 0; 82 }
有没有感觉很恶心，慢慢来吧。
【模板】线段树 2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。