题目描述

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

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）

 

根据加减法原理，，

好像只能这么解释，

先放乘法标记

再放加法标记

注意查询的时候ll和rr是不变的

1 #include
        
           2 #include
         
            3 #include
          
             4 #include
           
              5 #define LLI long long   6 using namespace std;  7 const LLI MAXN=400001;  8 LLI read(LLI & n)  9 { 10     char p='+';LLI x=0; 11     while(p<'0'||p>'9') 12         p=getchar(); 13     while(p>='0'&&p<='9') 14     x=x*10+p-48,p=getchar(); 15     n=x; 16 } 17 LLI n,m,mod,wl,wr,wv,ans; 18 struct node 19 { 20     LLI l,r,w,fc,fj; 21 }a[MAXN]; 22 void update(LLI k) 23 { 24     a[k].w=(a[k<<1].w+a[k<<1|1].w)%mod; 25 } 26 void build_tree(LLI k,LLI ll,LLI rr) 27 { 28     a[k].l=ll;a[k].r=rr; 29     a[k].fc=1; 30     a[k].fj=0; 31     if(a[k].l==a[k].r) 32     { 33         read(a[k].w); 34         return ; 35     } 36     LLI mid=(ll+rr)/2; 37     build_tree(k<<1,ll,mid); 38     build_tree(k<<1|1,mid+1,rr); 39     update(k); 40 } 41 void pushdown(LLI k,LLI ll,LLI rr,LLI mid) 42 { 43     a[k<<1].w*=a[k].fc;a[k<<1|1].w*=a[k].fc; 44     a[k<<1].w+=a[k].fj*(mid-ll+1);a[k<<1|1].w+=a[k].fj*(rr-mid); 45     a[k<<1].fc*=a[k].fc;a[k<<1|1].fc*=a[k].fc; 46     a[k<<1].fj*=a[k].fc;a[k<<1|1].fj*=a[k].fc; 47     a[k<<1].fj+=a[k].fj;a[k<<1|1].fj+=a[k].fj; 48     a[k].fc=1;a[k].fj=0; 49     a[k<<1].w%=mod;a[k<<1].fj%=mod;a[k<<1].fc%=mod; 50     a[k<<1|1].w%=mod;a[k<<1|1].fj%=mod;a[k<<1|1].fc%=mod; 51 } 52 void interval_add(LLI k,LLI ll,LLI rr,LLI v) 53 { 54     if(a[k].l>rr||a[k].r
            
             =a[k].r) 57     { 58         a[k].w=(a[k].w+v*(a[k].r-a[k].l+1))%mod; 59         a[k].fj=(a[k].fj+v)%mod; 60         return ; 61     } 62     LLI mid=(a[k].l+a[k].r)/2; 63     pushdown(k,a[k].l,a[k].r,mid); 64     //if(ll<=mid) 65     interval_add(k<<1,ll,rr,v); 66     //if(rr>mid) 67     interval_add(k<<1|1,ll,rr,v); 68     update(k); 69 } 70 void interval_mul(LLI k,LLI ll,LLI rr,LLI v) 71 { 72     if(a[k].l>rr||a[k].r
             
              =a[k].r) 75 { 76 a[k].w*=v%mod; 77 a[k].fc*=v%mod; 78 a[k].fj*=v%mod; 79 return ; 80 } 81 LLI mid=(a[k].l+a[k].r)/2; 82 pushdown(k,a[k].l,a[k].r,mid); 83 //if(ll<=mid) 84 interval_mul(k<<1,ll,rr,v); 85 //if(rr>mid) 86 interval_mul(k<<1|1,ll,rr,v); 87 update(k); 88 } 89 void interval_sum(LLI k,LLI ll,LLI rr) 90 { 91 if(a[k].l>rr||a[k].r
              
               =a[k].r) 94 { 95 ans=(ans+a[k].w)%mod; 96 return ; 97 } 98 LLI mid=(a[k].l+a[k].r)/2; 99 pushdown(k,a[k].l,a[k].r,mid);100 //if(ll<=mid)101 interval_sum(k<<1,ll,rr);102 //if(rr>mid)103 interval_sum(k<<1|1,ll,rr);104 }105 int main()106 {107 read(n);read(m);read(mod);108 build_tree(1,1,n);109 for(LLI i=1;i<=m;i++)110 {111 LLI p;112 read(p);113 if(p==1)114 {115 read(wl);read(wr);read(wv);116 interval_mul(1,wl,wr,wv);117 }118 else if(p==2)119 {120 read(wl);read(wr);read(wv);121 interval_add(1,wl,wr,wv);122 }123 else if(p==3)124 {125 ans=0;126 read(wl);read(wr);127 interval_sum(1,wl,wr);128 //cout<
               
                <