【数据结构】——线段树板子

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 int read(){
  5     int x=0,f=1;
  6     char c=getchar();
  7     while(!isdigit(c)){
  8         if(c=='-') f=-1;
  9         c=getchar();
 10     }
 11     while(isdigit(c)){
 12         x=(x<<1)+(x<<3)+(c^48);
 13         c=getchar();
 14     }
 15     return x*f;
 16 }
 17 const int N=1e5+10;
 18 int n,m,p;
 19 int a[N];
 20 struct tree{
 21     ll sum[N<<2];
 22     ll add[N<<2],mul[N<<2];
 23     int ls(int o){return o<<1;}
 24     int rs(int o){return o<<1|1;}
 25     void pushup(int o){
 26         sum[o]=(sum[ls(o)]+sum[rs(o)])%p;
 27     }
 28     void pushdown(int o,int l,int r){
 29         int mid=(l+r)>>1;
 30         sum[ls(o)]=(sum[ls(o)]*mul[o]+add[o]*(mid-l+1))%p;
 31         sum[rs(o)]=(sum[rs(o)]*mul[o]+add[o]*(r - mid))%p;
 32         mul[ls(o)]=(mul[ls(o)]*mul[o])%p;
 33         mul[rs(o)]=(mul[rs(o)]*mul[o])%p;
 34         add[ls(o)]=(add[ls(o)]*mul[o]+add[o])%p;
 35         add[rs(o)]=(add[rs(o)]*mul[o]+add[o])%p;
 36         mul[o]=1;add[o]=0;
 37     }
 38     void build(int o,int l,int r){
 39         add[o]=0,mul[o]=1;
 40         if(l==r){
 41             sum[o]=a[l];
 42             return;
 43         }
 44         int mid=(l+r)>>1;
 45         build(ls(o),l,mid);
 46         build(rs(o),mid+1,r);
 47         pushup(o);
 48     }
 49     void multi(int o,int l,int r,int x,int y,ll k){
 50         if(l>y||r<x) return;
 51         if(l>=x&&r<=y){
 52             sum[o]=(sum[o]*k)%p;
 53             add[o]=(add[o]*k)%p;
 54             mul[o]=(mul[o]*k)%p;
 55             return;
 56         }
 57         int mid=(l+r)>>1;
 58         pushdown(o,l,r);
 59         if(x<=mid) multi(ls(o),l,mid,x,y,k);
 60         if(r>mid) multi(rs(o),mid+1,r,x,y,k);
 61         pushup(o);
 62     }
 63     void plus(int o,int l,int r,int x,int y,ll k){
 64         if(l>y||r<x) return;
 65         if(l>=x&&r<=y){
 66             sum[o]=(sum[o]+k*(r-l+1))%p;
 67             add[o]=(add[o]+k)%p;
 68             return;
 69         }
 70         int mid=(l+r)>>1;
 71         pushdown(o,l,r);
 72         if(x<=mid) plus(ls(o),l,mid,x,y,k);
 73         if(r>mid) plus(rs(o),mid+1,r,x,y,k);
 74         pushup(o);
 75     }
 76     ll query(int o,int l,int r,int x,int y){
 77         if(l>y||r<x) return 0;
 78         if(l>=x&&r<=y){
 79             return sum[o];
 80         }
 81         int mid=(l+r)>>1;
 82         pushdown(o,l,r);
 83         return (query(rs(o),mid+1,r,x,y)+query(ls(o),l,mid,x,y))%p;
 84     }
 85 }t;
 86 int main(){
 87     n=read();p=read();
 88     for(int i=1;i<=n;i++){
 89         a[i]=read();
 90     }
 91     m=read();
 92     t.build(1,1,n);
 93     int num,x,y;
 94     ll k;
 95     for(int i=1;i<=m;i++){
 96         num=read();x=read();y=read();
 97         if(num==1){
 98             k=read();
 99             t.multi(1,1,n,x,y,k);
100         }
101         else if(num==2){
102             k=read();
103             t.plus(1,1,n,x,y,k);
104         }
105         else{
106             printf("%lld
",t.query(1,1,n,x,y));
107         }
108     }
109     return 0;
110 }
用我优美的能看的过去的代码格式打一份板子放这了。
——抓住了时间，却不会利用的人，终究也逃不过失败的命运。