@[FCJ666](/user/376827) 给你看看封装好的线段树：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9,ROOT = 1;
int a[N];
int n,m,p;
int op,x,y,k;
struct seg_tree{
struct node {
int val,add,mul;
} tree[N << 2];
bool in_range(int l,int r,int now_l,int now_r){
return l <= now_l && now_r <= r;
}
bool out_range(int l,int r,int now_l,int now_r){
return now_r < l || now_l > r;
}
int len(int l,int r){
return r - l + 1;
}
void push_up(int root){
int lchild = root * 2,rchild = root * 2 + 1;
tree[root].val = (tree[lchild].val + tree[rchild].val) % p;
}
void make_tag(int Len,int root,int k,int type){
if(type == 1){
tree[root].add = (tree[root].add * k) % p;
tree[root].mul = (tree[root].mul * k) % p;
tree[root].val = (tree[root].val * k) % p;
}
else{
tree[root].add = (tree[root].add + k) % p;
tree[root].val = (tree[root].val + Len * k) % p;
}
}
void push_down(int l,int r,int root){
int mid = (l + r) / 2,lchild = root * 2,rchild = root * 2 + 1;
make_tag(len(l,mid),lchild,tree[root].mul,1);
make_tag(len(l,mid),lchild,tree[root].add,2);
make_tag(len(mid + 1,r),rchild,tree[root].mul,1);
make_tag(len(mid + 1,r),rchild,tree[root].add,2);
tree[root].mul = 1;
tree[root].add = 0;
}
void build(int l,int r,int root) {
tree[root].mul = 1;
if(l == r) {
tree[root].val = a[l] % p;
return;
}
int mid = (l + r) / 2,lchild = root * 2,rchild = root * 2 + 1;
build(l,mid,lchild);
build(mid + 1,r,rchild);
push_up(root);
}
void update(int l,int r,int now_l,int now_r,int root,int k,int type) {
if(in_range(l,r,now_l,now_r))
make_tag(len(now_l,now_r),root,k,type);
else if(!out_range(l,r,now_l,now_r)){
int mid = (now_l + now_r) / 2,lchild = root * 2,rchild = root * 2 + 1;
push_down(now_l,now_r,root);
update(l,r,mid + 1,now_r,rchild,k,type);
update(l,r,now_l,mid,lchild,k,type);
push_up(root);
}
return;
}
int getsum(int l, int r, int now_l, int now_r, int root) {
int mid = (now_l + now_r) / 2,lchild = root * 2,rchild = root * 2 + 1;
if(in_range(l,r,now_l,now_r))
return tree[root].val;
else if(!out_range(l,r,now_l,now_r)){
push_down(now_l,now_r,root);
return (getsum(l,r,now_l,mid,lchild) + getsum(l,r,mid + 1,now_r,rchild)) % p;
}
else
return 0;
}
} seg;
signed main() {
scanf("%lld%lld%lld", &n, &m, &p);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
seg.build(1,n,ROOT);
for(int i = 1; i <= m; i++) {
scanf("%lld%lld%lld", &op, &x, &y);
if(op == 1 || op == 2) {
scanf("%lld" ,&k);
seg.update(x,y,1,n,ROOT,k,op);
}
else
printf("%lld\n", seg.getsum(x,y,1,n,ROOT));
}
}
```
by 5t0_0r2 @ 2023-08-30 15:50:38