洛谷3372线段树模板

题目链接：https://www.luogu.com.cn/problem/P3372

题目是经典的线段树模板题，要求支持三种操作：①、查询区间和取模的值 ②、给指定区间加上一个值 ③、给指定区间乘上一个值

只要明确先做乘标记在做加标记就解决了问题，因为先做加标记再做乘标记的话就会出现加标记是小数的情况，不好计算，代码中我已明确如何下推标记等。有一点不足就是取模的耗费是非常巨大的，柯匡取模这么多次，我的用时大约是2300ms，是洛谷最优ac时间的三倍，模板写的还是很差劲的。

代码如下：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef unsigned int ui;
  4 typedef long long ll;
  5 typedef unsigned long long ull;
  6 #define pf printf
  7 #define mem(a,b) memset(a,b,sizeof(a))
  8 #define prime1 1e9+7
  9 #define prime2 1e9+9
 10 #define pi 3.14159265
 11 #define lson l,mid,rt<<1
 12 #define rson mid+1,r,rt<<1|1
 13 #define scand(x) scanf("%llf",&x) 
 14 #define f(i,a,b) for(int i=a;i<=b;i++)
 15 #define scan(a) scanf("%d",&a)
 16 #define dbg(args) cout<<#args<<":"<<args<<endl;
 17 #define pb(i) push_back(i)
 18 #define ppb(x) pop_back(x)
 19 #define inf 0x3f3f3f3f
 20 #define maxn 100005
 21 int n,m;
 22 ll p;
 23 ll sum[maxn<<2],add[maxn<<2],mul[maxn<<2];
 24 //维护的区间形式上是 sum*mul+add 
 25 void pushup(int rt)
 26 {
 27     sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%p;
 28 }
 29 void pushdown(int l,int r,int rt)
 30 {
 31     int mid=l+r>>1;
 32         mul[rt<<1]=(mul[rt<<1]*mul[rt])%p;//先推乘法标记，再推加法标记 
 33         mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%p;
 34         sum[rt<<1]=(sum[rt<<1]*mul[rt]+add[rt]*(mid-l+1))%p;
 35         sum[rt<<1|1]=(sum[rt<<1|1]*mul[rt]+add[rt]*(r-mid))%p;
 36         add[rt<<1]=(add[rt<<1]*mul[rt]+add[rt])%p;
 37         add[rt<<1|1]=(add[rt<<1|1]*mul[rt]+add[rt])%p;
 38         mul[rt]=1;
 39         add[rt]=0;
 40  } 
 41 void build(int l,int r,int rt)
 42 {
 43     mul[rt]=1;//注意所有的区间段都要是mul=1,并不是只有最下层的点才有mul=1; 
 44     if(l==r)
 45     {
 46         scanf("%lld",&sum[rt]);
 47     //    mul[rt]=1;
 48         return ;
 49     }
 50     int mid=l+r>>1;
 51     build(lson);
 52     build(rson);
 53     pushup(rt);
 54 }
 55 ll query(int l,int r,int rt,int L,int R)
 56 {
 57     if(L<=l&&r<=R)
 58     {
 59         return sum[rt];
 60     }
 61     int mid=l+r>>1;
 62     ll ans=0;
 63     pushdown(l,r,rt);
 64     if(L<=mid)    ans=query(lson,L,R)%p;
 65     if(R>mid) ans=(ans+query(rson,L,R))%p;
 66     return ans;
 67 }
 68 void update_add(int l,int r,int rt,int L,int R,int C)
 69 {
 70     if(L<=l&&r<=R)
 71     {
 72         sum[rt]=(sum[rt]+C*(r-l+1))%p;
 73         add[rt]=(add[rt]+C)%p;
 74         return;
 75     }
 76     int mid=l+r>>1;
 77     pushdown(l,r,rt);//懒标记下推，否则下面区间的更新是错误的 
 78     if(L<=mid) update_add(lson,L,R,C);
 79     if(R>mid) update_add(rson,L,R,C);
 80     pushup(rt);
 81 }
 82 void update_mul(int l,int r,int rt,int L,int R,int C)
 83 {
 84     if(L<=l&&r<=R)  
 85     //区间值是 sum=a*mul+add,则*C之后mul<-mul*C,add<-add*C，sum<-sum*C;
 86     //即sum*C=a*mul*C+add*C 
 87     {
 88         sum[rt]=(sum[rt]*C)%p;
 89         add[rt]=(add[rt]*C)%p;
 90         mul[rt]=(mul[rt]*C)%p;
 91         return;
 92     }
 93     int mid=l+r>>1;
 94     pushdown(l,r,rt);
 95     if(L<=mid) update_mul(lson,L,R,C);
 96     if(R>mid) update_mul(rson,L,R,C);
 97     pushup(rt);
 98 }
 99 int main()
100 {
101     //freopen("input.txt","r",stdin);
102     //freopen("output.txt","w",stdout);
103     std::ios::sync_with_stdio(false);
104     scan(n);
105     scanf("%lld",&p);
106     build(1,n,1);
107     scan(m);
108     int op,l,r,c;
109     while(m--)
110     {
111         scan(op);
112         if(op==1)
113         {
114             scanf("%d%d%d",&l,&r,&c);
115             update_mul(1,n,1,l,r,c);
116         }
117         else if(op==2)
118         {
119             scanf("%d%d%d",&l,&r,&c);
120             update_add(1,n,1,l,r,c);
121         }
122         else if(op==3)
123         {
124             scanf("%d%d",&l,&r);
125             pf("%lld
",query(1,n,1,l,r));
126         }
127     }
128  }