线段树の二 区间乘+区间加
具体就不解释了，看上一篇文章
放代码
注意点：！！！！
注意运算符优先级
比如：
a*=b%p 是b先mod p再与a相乘
a<<1+1是1+1再a位移
a<<1=a*2
a<<1|1=a*2+1
/*******************************
线段树V2.0
支持区间加、区间乘、区间和查询
********************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1000010
using namespace std;
struct node
{
int left;//节点所代表区间左端
int right;//节点所代表区间右端
long long sum;//区间和
long long add;//区间加Lazy标记
long long mult;//区间乘Lazy标记
node(){mult=1;}
} tree[N];
long long a[N];
int n,m,p;//n:区间大小 m:操作次数 p:取模
//left:当前区间左端 right:当前区间右端 node:当前节点
void Build_Tree(int left,int right,int node)
{
tree[node].left=left;
tree[node].right=right;
if(left==right) tree[node].sum=a[left];
else
{
int mid=(left+right)>>1;
Build_Tree(left,mid,node<<1);
Build_Tree(mid+1,right,node<<1|1);
tree[node].sum=(tree[node<<1].sum+tree[node<<1|1].sum)%p;
}
}
//标记下放 node:当前节点
void Push_Down(int node)
{
if(tree[node].add==0&&tree[node].mult==1) return;
tree[node<<1].mult=tree[node<<1].mult*tree[node].mult%p;
tree[node<<1|1].mult=tree[node<<1|1].mult*tree[node].mult%p;
tree[node<<1].add=tree[node<<1].add*tree[node].mult%p;
tree[node<<1|1].add=tree[node<<1|1].add*tree[node].mult%p;
tree[node<<1].sum=tree[node<<1].sum*tree[node].mult%p;
tree[node<<1|1].sum=tree[node<<1|1].sum*tree[node].mult%p;
tree[node].mult=1;
tree[node<<1].add=(tree[node<<1].add+tree[node].add)%p;
tree[node<<1|1].add=(tree[node<<1|1].add+tree[node].add)%p;
tree[node<<1].sum=(tree[node<<1].sum+tree[node].add*(tree[node<<1].right-tree[node<<1].left+1))%p;
tree[node<<1|1].sum=(tree[node<<1|1].sum+tree[node].add*(tree[node<<1|1].right-tree[node<<1|1].left+1))%p;
tree[node].add=0;
}
//上推 node:当前节点
void Push_Up(int node)
{
tree[node].sum=(tree[node<<1].sum+tree[node<<1|1].sum)%p;
}
//区间加操作 left:操作区间左端点 right:操作区间右端点 node:当前节点 value:操作值
void Add_Range(int left,int right,int node,long long value)
{
if(tree[node].left>=left&&tree[node].right<=right)
{
tree[node].add+=value%p;
tree[node].sum+=value*(tree[node].right-tree[node].left+1)%p;
return;
}
Push_Down(node);
int mid=(tree[node].left+tree[node].right)>>1;
if(left<=mid) Add_Range(left,right,node<<1,value);
if(right>mid) Add_Range(left,right,node<<1|1,value);
Push_Up(node);
}
//区间乘操作 left:操作区间左端点 right:操作区间右端点 node:当前节点 value:操作值
void Mult_Range(int left,int right,int node,long long value)
{
if(tree[node].left>=left&&tree[node].right<=right)
{
tree[node].mult=tree[node].mult*value%p;
tree[node].add=tree[node].add*value%p;
tree[node].sum=tree[node].sum*value%p;
return;
}
Push_Down(node);
int mid=(tree[node].left+tree[node].right)>>1;
if(left<=mid) Mult_Range(left,right,node<<1,value);
if(right>mid) Mult_Range(left,right,node<<1|1,value);
Push_Up(node);
}
//区间和查询 left:查询区间左端点 right:查询区间右端点 node:当前节点
long long Query_Sum(int left,int right,int node)
{
if(tree[node].left>right||tree[node].right<left)
return 0;
Push_Down(node);
if(tree[node].left>=left&&tree[node].right<=right)
return tree[node].sum%p;
return (Query_Sum(left,right,node*2)+Query_Sum(left,right,node*2+1))%p;
}
int main()
{
cin>>n>>m>>p;
for(int i=1; i<=n; i++) cin>>a[i];
Build_Tree(1,n,1);
while(m--)
{
int x,y,c;
cin>>c>>x>>y;
if(c==1)//区间乘操作
{
long long v;
cin>>v;
Mult_Range(x,y,1,v);
}
if(c==2)//区间加操作
{
long long v;
cin>>v;
Add_Range(x,y,1,v);
}
if(c==3)//查询
cout<<Query_Sum(x,y,1)<<endl;
}
return 0;
}