首页 > 代码库 > 线段树的进阶使用（洛谷3373 ）

线段树的进阶使用（洛谷3373 ）

2024-09-24 00:15:38   220人阅读

题目描述

如题，已知一个数列，你需要进行下面两种操作：

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
按照题目模拟即可，写乘法运算的时候请记得注意以下的小细节:
1.乘法的数组的初始值要设为1，不然系统默认为0做乘法的时候是没有意义的~
2.要注意位运算的使用，在别代码中，二进制的迅速是无法替代的
3.加法和乘法的运算顺序要把握好，乘在先，加在后
4.PushDown函数的加法和乘法需要写在一起，不然前者会把后者的覆盖住，这样就会对后面的产生干扰
5.养成好习惯，做一步，取模一步
前车之鉴，后车之师，下面放上代码，当当当~~（在这里感谢大佬封癫（U25815 ）以及 yql的信徒的热切帮助~）
  1 #include<bits/stdc++.h>
  2 #define maxn 1000007
  3 #define LL long long
  4 using namespace std;
  5 LL n,m;
  6 LL c[4*maxn],a[maxn];
  7 LL add[maxn];
  8 LL P;
  9 LL addplus[maxn];
 10 void PushUp(LL rt)
 11 {
 12      c[rt]=c[rt<<1]+c[rt<<1|1];
 13      c[rt]%=P;
 14 }
 15 void Build(LL l,LL r,LL rt)
 16 {
 17      if(l==r)
 18      {
 19          c[rt]=a[l];
 20          return ;
 21      }
 22      LL m=(l+r)>>1;
 23      Build(l,m,rt<<1);
 24      Build(m+1,r,rt<<1|1);
 25      PushUp(rt);
 26 }
 27 void Pushdown(LL rt,LL ln,LL rn)
 28 {
 29    if((addplus[rt]==1)&&(!add[rt]))return ;//这里要用"&&"，如果满足一种情况也是要进行考虑的 
 30    
 31        addplus[rt<<1]=(addplus[rt<<1]*addplus[rt])%P;
 32        addplus[rt<<1|1]=(addplus[rt<<1|1]*addplus[rt])%P;
 33        c[rt<<1]=(c[rt<<1]*addplus[rt])%P;
 34        c[rt<<1|1]=(c[rt<<1|1]*addplus[rt])%P;
 35        
 36       add[rt<<1]=(add[rt<<1]*addplus[rt]+add[rt])%P;
 37       add[rt<<1|1]=(add[rt<<1|1]*addplus[rt]+add[rt])%P;
 38       c[rt<<1]=(c[rt<<1]+add[rt]*ln)%P;
 39       c[rt<<1|1]=(c[rt<<1|1]+add[rt]*rn)%P;
 40       
 41       add[rt]=0;
 42       addplus[rt]=1;
 43 }
 44 void Update_interval(LL L,LL R,LL C,LL l,LL r,LL  rt)
 45 {
 46     if(L<=l&&r<=R)
 47     {
 48       c[rt]+=C*(r-l+1);
 49       c[rt]%=P;
 50       add[rt]+=C;
 51       add[rt]%=P;
 52       return ;
 53    }
 54    LL m=(l+r)>>1;
 55    Pushdown(rt,m-l+1,r-m);
 56    if(L<=m) Update_interval(L,R,C,l,m,rt<<1);
 57    if(R>m) Update_interval(L,R,C,m+1,r,rt<<1|1);
 58    PushUp(rt);
 59    return ;
 60 }
 61 LL Query(LL L,LL R,LL l,LL r,LL rt)
 62 {
 63        if(L<=l&&r<=R)
 64           return c[rt];
 65       LL m=(l+r)>>1;
 66       LL ans=0;
 67       Pushdown(rt,m-l+1,r-m);
 68       if(L<=m) ans+=Query(L,R,l,m,rt<<1);
 69       if(R>m) ans+=Query(L,R,m+1,r,rt<<1|1);
 70       PushUp(rt);
 71       ans%=P;
 72       return ans;
 73 }
 74 void Update_intervalplus(LL L,LL R,LL C,LL l,LL r,LL rt)
 75 {
 76    if(L<=l&&r<=R)
 77     {
 78       c[rt]*=C;
 79       c[rt]%=P;
 80       add[rt]*=C;
 81       add[rt]%=P;
 82       addplus[rt]*=C;
 83       addplus[rt]%=P;
 84       return ;
 85    }
 86    LL m=(l+r)>>1;
 87    Pushdown(rt,m-l+1,r-m);
 88    if(L<=m) Update_intervalplus(L,R,C,l,m,rt<<1);
 89    if(R>m) Update_intervalplus(L,R,C,m+1,r,rt<<1|1);
 90    PushUp(rt);
 91    return ;
 92 }
 93 
 94 int main()
 95 {
 96     ios::sync_with_stdio(false);//这句话一定要加上，不然c++的输入输出太慢了。 
 97     cin>>n>>m;
 98     for(int i=0;i<=maxn;i++)
 99       addplus[i]=1;
100     cin>>P;
101     for(LL i=1;i<=n;i++)
102       cin>>a[i];
103       Build(1,n,1);
104       LL t1,t2,t3,t4;
105     for(LL  i=1;i<=m;i++)
106     {
107          cin>>t1;
108          if(t1==1)
109          {
110             cin>>t2>>t3>>t4;
111             Update_intervalplus(t2,t3,t4,1,n,1);
112          }
113          if(t1==2)
114           { 
115                   cin>>t2>>t3>>t4;
116                   Update_interval(t2,t3,t4,1,n,1);
117           }
118           if(t1==3)
119           {
120              cin>>t2>>t3;
121              cout<<(Query(t2,t3,1,n,1))%P<<endl;
122           }
123     }  
124     return 0;
125 }

 





线段树的进阶使用（洛谷3373 ）


联系
我们