真神奇洛谷A，信友队WA0
#include<bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
int m,n,mod;
int tree[N<<2],tree2[N<<2],sumt[N<<2];
inline void pushup(int id){
sumt[id]=(sumt[id<<1]+sumt[id<<1|1])%mod;
}
inline void build(int id,int l,int r){
tree2[id]=1;
if(l==r){
cin>>sumt[id];
return;
}
int mid=l+r>>1;
build(id<<1,l,mid),build(id<<1|1,mid+1,r),pushup(id);
}
inline void push(int id,int L,int v){
(tree[id]+=v)%=mod,(sumt[id]+=L*v)%=mod;
}
inline void push2(int id,int v){
(tree[id]*=v)%=mod,(tree2[id]*=v)%=mod,(sumt[id]*=v)%=mod;
}
inline void pushdown(int id,int l,int r){
int mid=l+r>>1;
if(tree2[id]!=1){
push2(id<<1,tree2[id]),push2(id<<1|1,tree2[id]),tree2[id]=1;
}
if(tree[id]){
push(id<<1,mid-l+1,tree[id]),push(id<<1|1,r-mid,tree[id]),tree[id]=0;
}
}
inline void change1(int id,int l,int r,int x,int y,int v){
if(l>=x&&r<=y)return push2(id,v);
pushdown(id,l,r);int mid=l+r>>1;
if(x<=mid)change1(id<<1,l,mid,x,y,v);
if(y>mid)change1(id<<1|1,mid+1,r,x,y,v);
pushup(id);
}
inline void change2(int id,int l,int r,int x,int y,int v)
{
if(l>=x&&r<=y)return push(id,r-l+1,v);
pushdown(id,l,r);int mid=l+r>>1;
if(x<=mid)change2(id<<1,l,mid,x,y,v);
if(y>mid)change2(id<<1|1,mid+1,r,x,y,v);
pushup(id);
}
inline int ans(int id,int l,int r,int x,int y)
{
if(l>=x&&r<=y)return sumt[id];
pushdown(id,l,r);int tans=0,mid=l+r>>1;
if(x<=mid)tans+=ans(id<<1,l,mid,x,y);
if(y>mid)tans+=ans(id<<1|1,mid+1,r,x,y);
return tans%mod;
}
signed main()
{
cin>>n>>m>>mod;
build(1,1,n);
for(int i=1,x,l,r;i<=m;i++){
cin>>x>>l>>r;
int k;
if(x!=3){
cin>>k;
}
if(x==1)change1(1,1,n,l,r,k);
if(x==2)change2(1,1,n,l,r,k);
if(x==3)cout<<ans(1,1,n,l,r)<<"\n";
}
return 0;
}
题目描述
如题，已知一个数列，你需要进行下面三种操作：
将某区间每一个数乘上 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≤1e3，m≤1e4
对于 100% 的数据：n≤1e5，m≤1e5，p=571373 k≤1e18。