4. 线段树2
题目ID：7337必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
如题，已知一个数列，你需要进行下面三种操作：
- 将某区间每一个数乘上 x
- 将某区间每一个数加上 x
- 求出某区间每一个数的和
输入格式：
第一行包含三个整数 n,m,p，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含若干个整数，表示一个操作，具体如下：
操作 1： 格式：
1 x y k含义：将区间 [x,y] 内每个数乘上 k操作 2： 格式：
2 x y k含义：将区间 [x,y] 内每个数加上 k操作 3： 格式：
3 x y含义：输出区间 [x,y] 内每个数的和对 p 取模所得的结果样例：
输入：
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
输出：
17 2
数据规模：
对于 30% 的数据：n≤103，m≤104
对于 100% 的数据：n≤105，m≤105，p=571373 k≤1e18。
一百多行代码：
#include<bits/stdc++.h>
#define ll long long
#define cz1 (pos<<1)
#define cz2 (pos<<1|1)
using namespace std;
const int N=100005;
int n,m,mod;
int a[N];
struct s_tree{
ll sum,add,mul;
int l,r;
}s[N*4];
void upd(int pos){
int kk=cz1;
int mm=cz2;
s[pos].sum=(s[kk].sum+s[mm].sum)%mod;
return;
}
void push_down(int pos){
int kk=cz1;
int mm=cz2;
s[kk].sum=(s[kk].sum*s[pos].mul+s[pos].add*(s[kk].r-s[kk].l+1))%mod;
s[mm].sum=(s[mm].sum*s[pos].mul+s[pos].add*(s[mm].r-s[mm].l+1))%mod;
s[kk].mul=(s[kk].mul*s[pos].mul)%mod;
s[mm].mul=(s[mm].mul*s[pos].mul)%mod;
s[kk].add=(s[kk].add*s[pos].mul+s[pos].add)%mod;
s[mm].add=(s[mm].add*s[pos].mul+s[pos].add)%mod;
s[pos].add=0;
s[pos].mul=1;
return;
}
void bld_tree(int pos,int l,int r){
s[pos].l=l;
s[pos].r=r;
s[pos].mul=1;
if(l==r){
s[pos].sum=a[l]%mod;
return;
}
int mid=(l+r)>>1;
int kk=cz1;
int mm=cz2;
bld_tree(kk,l,mid);
bld_tree(mm,mid+1,r);
upd(pos);
return;
}
void cm(int pos,int x,int y,int k){
if(x<=s[pos].l&&s[pos].r<=y){
s[pos].add=(s[pos].add*k)%mod;
s[pos].mul=(s[pos].mul*k)%mod;
s[pos].sum=(s[pos].sum*k)%mod;
return;
}
push_down(pos);
int kk=cz1;
int mm=cz2;
int mid=(s[pos].l+s[pos].r)>>1;
if(x<=mid){
cm(kk,x,y,k);
}
if(y>mid){
cm(mm,x,y,k);
}
upd(pos);
return;
}
void ca(int pos,int x,int y,int k){ //区间加法
if(x<=s[pos].l&&s[pos].r<=y){
s[pos].add=(s[pos].add+ k)%mod;
s[pos].sum=(s[pos].sum+k*(s[pos].r-s[pos].l+1))%mod;
return;
}
push_down(pos);
int kk=cz1;
int mm=cz2;
int mid=(s[pos].l+s[pos].r)>>1;
if(x<=mid){
ca(kk,x,y,k);
}
if(y>mid){
ca(mm,x,y,k);
}
upd(pos);
return;
}
ll ask_r(int pos,int x,int y){
if(x<=s[pos].l&&s[pos].r<=y){
return s[pos].sum;
}
push_down(pos);
int kk=cz1;
int mm=cz2;
ll val=0;
int mid=(s[pos].l+s[pos].r)>>1;
if(x<=mid){
val=(val+ask_r(kk,x,y))%mod;
}
if(y>mid){
val=(val+ask_r(mm,x,y))%mod;
}
return val;
}
int main(){
scanf("%d%d%d",&n,&m,&mod);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
bld_tree(1,1,n);
for(int i=1;i<=m;i++){
int cz,x,y;
scanf("%d%d%d",&cz,&x,&y);
if(cz==1){
int k;
scanf("%d",&k);
cm(1,x,y,k);
}
else if(cz==2){
int k;
scanf("%d",&k);
ca(1,x,y,k);
}
else{
cout<<ask_r(1,x,y)<<endl;
}
}
return 0;
}
/*
*/
