如题,已知一个数列,你需要进行下面两种操作:
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
时空限制: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<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
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<ll)
55 return ;
56 if(ll<=a[k].l&&rr>=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<ll)
73 return ;
74 if(ll<=a[k].l&&rr>=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<ll)
92 return ;
93 if(ll<=a[k].l&&rr>=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<<ans%mod<<endl;
129 printf("%lld\n",ans%mod);
130 }
131 }
132 return 0;
133 }