首页 > 代码库 > 【原创】洛谷 LUOGU P3373 【模板】线段树2

【原创】洛谷 LUOGU P3373 【模板】线段树2

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)

 
乘法的优先级永远比加法高。
代码如下:
  1 // LUOGU 3373 【模板】线段树2   2 // 2017.7.20 20:52  3 #include<bits/stdc++.h>  4 #define INF 0x3fffffff  5 #define MAXN 100000  6 #define MAXT MAXN*4  7 using namespace std;  8 typedef long long ll;  9 int N,M,topt=0; 10 ll P,a[MAXN+2]; 11 struct sgt_node{ 12     int lc,rc; 13     ll sum,pls,mul; 14     sgt_node(){pls=0,mul=INF;} 15 }sgt[MAXT+2]; 16 int getint(){ 17     char ch=*; 18     while(!isdigit(ch=getchar())); 19     int num=ch-0; 20     while(isdigit(ch=getchar()))num=num*10+ch-0; 21     return num; 22 } 23 ll getll(){ 24     char ch=*; 25     while(!isdigit(ch=getchar())); 26     ll num=ch-0; 27     while(isdigit(ch=getchar()))num=num*10+ch-0; 28     return num; 29 } 30 #define lch sgt[now].lc 31 #define rch sgt[now].rc 32 #define smid ((l+r)>>1) 33 void update(int now){ 34     sgt[now].sum=(sgt[lch].sum+sgt[rch].sum)%P; 35 } 36 void set_mul(int now,ll v){ 37     sgt[now].sum=(sgt[now].sum*v)%P; 38     if(sgt[now].mul==INF)sgt[now].mul=v%P; 39     else sgt[now].mul=(sgt[now].mul*v)%P;  // 必须为乘法!!! 40     sgt[now].pls=(sgt[now].pls*v)%P; 41 } 42 void set_pls(int now,int l,int r,ll v){ 43     sgt[now].sum=(sgt[now].sum+v*(r-l+1))%P; 44     sgt[now].pls=(sgt[now].pls+v)%P; 45 } 46 void push_down(int now,int l,int r){ 47     if(sgt[now].mul!=INF){ 48         set_mul(lch,sgt[now].mul); 49         set_mul(rch,sgt[now].mul); 50         sgt[now].mul=INF; 51     } 52     if(sgt[now].pls){ 53         set_pls(lch,l,smid,sgt[now].pls); 54         set_pls(rch,smid+1,r,sgt[now].pls); 55         sgt[now].pls=0; 56     } 57 } 58 void Build_sgt(int &now,int l,int r){ 59     now=++topt; 60     if(l==r){ 61         sgt[now].sum=a[l]; 62         return; 63     } 64     Build_sgt(lch,l,smid); 65     Build_sgt(rch,smid+1,r); 66     update(now); 67 } 68 ll Query_sgt(int now,int l,int r,int qx,int qy){ 69     if(l==qx&&r==qy)return sgt[now].sum; 70     push_down(now,l,r); 71     if(qy<=smid)return Query_sgt(lch,l,smid,qx,qy); 72     if(qx>smid)return Query_sgt(rch,smid+1,r,qx,qy); 73     return Query_sgt(lch,l,smid,qx,smid)+Query_sgt(rch,smid+1,r,smid+1,qy); 74 } 75 void Region_mul(int now,int l,int r,int x,int y,ll v){ 76     if(l==x&&r==y){ 77         set_mul(now,v); 78         return; 79     } 80     push_down(now,l,r); 81     if(y<=smid)Region_mul(lch,l,smid,x,y,v); 82     else if(x>smid)Region_mul(rch,smid+1,r,x,y,v); 83     else{ 84         Region_mul(lch,l,smid,x,smid,v); 85         Region_mul(rch,smid+1,r,smid+1,y,v); 86     } 87     update(now); 88 } 89 void Region_pls(int now,int l,int r,int x,int y,ll v){ 90     if(l==x&&r==y){ 91         set_pls(now,l,r,v); 92         return; 93     } 94     push_down(now,l,r); 95     if(y<=smid)Region_pls(lch,l,smid,x,y,v); 96     else if(x>smid)Region_pls(rch,smid+1,r,x,y,v); 97     else{ 98         Region_pls(lch,l,smid,x,smid,v); 99         Region_pls(rch,smid+1,r,smid+1,y,v);100     }101     update(now);102 }103 int main(){104     N=getint(),M=getint(),P=getll();105     for(int i=1;i<=N;i++)106         a[i]=getll();107     int root=0;108     Build_sgt(root,1,N);109     int op,x,y;110     ll k;111     for(int i=1;i<=M;i++){112         op=getint();113         switch(op){114             case 1:115                 x=getint(),y=getint(),k=getll();116                 Region_mul(1,1,N,x,y,k);117                 break;118             case 2:119                 x=getint(),y=getint(),k=getll();120                 Region_pls(1,1,N,x,y,k);121                 break;122             case 3:123                 x=getint(),y=getint();124                 printf("%lld\n",Query_sgt(1,1,N,x,y)%P);125                 break;126         }127     }    128     return 0;129 }

 

<script type="text/javascript" src="https://cdn.bootcss.com/amazeui/2.7.2/js/amazeui.min.js"></script><script type="text/javascript" src="https://cdn.bootcss.com/highcharts/5.0.12/highcharts.js"></script><script type="text/javascript" src="http://cdn.luogu.org/js/luogu3.js?ver=20170628"></script><script type="text/javascript" src="https://www.google.com/recaptcha/api.js?hl=zh-CN&render=explicit" defer="defer"></script>

【原创】洛谷 LUOGU P3373 【模板】线段树2