萌新求助线段树
运行是正确的 但是答案是错的
#include <iostream>
#include <cstdio>
typedef long long ll;
const int MAXN = 1e5+10;
struct Tree{
int l, r;
ll val, sign1, sign2;
}t[MAXN*4];
int n, m;
ll s[MAXN], p;
#define ls (k*2)
#define rs (k*2+1)
void build(int k, int l, int r){
t[k].l = l, t[k].r = r;
t[k].sign1 = 1;
if(l==r){
t[k].val = s[l]%p;
return;
}
int mid = (l+r)>>1;
build(ls, l, mid);
build(rs, mid+1, r);
t[k].val = (t[ls].val+t[rs].val)%p;
}
void spread(int k){
if(t[k].sign1!=1){
t[ls].val = t[ls].val*t[k].sign1%p;
t[rs].val = t[rs].val*t[k].sign1%p;
t[ls].sign1 = t[ls].sign1*t[k].sign1%p;
t[rs].sign1 = t[rs].sign1*t[k].sign1%p;
t[k].sign1 = 1;
}
if(t[k].sign2){
t[ls].val = (t[ls].val+t[k].sign2*(t[ls].r-t[ls].l+1))%p;
t[rs].val = (t[rs].val+t[k].sign2*(t[rs].r-t[rs].l+1))%p;
t[ls].sign2 = (t[ls].sign2+t[k].sign2)%p;
t[rs].sign2 = (t[rs].sign2+t[k].sign2)%p;
t[k].sign2 = 0;
}
}
void modify1(int k, int l, int r, ll val){
if(l<=t[k].l && t[k].r<=r){
t[k].val = t[k].val*val%p;
t[k].sign1 = t[k].sign1*val%p;
return;
}
spread(k);
int mid = (t[k].l+t[k].r)>>1;
if(l<=mid)
modify1(ls, l, r, val);
if(r>mid)
modify1(rs, l, r, val);
t[k].val = (t[ls].val+t[rs].val)%p;
}
void modify2(int k, int l, int r, ll val){
if(l<=t[k].l && t[k].r<=r){
t[k].val = (t[k].val+val*(t[k].r-t[k].l+1))%p;
t[k].sign2 = (t[k].sign2+val)%p;
return;
}
spread(k);
int mid = (t[k].l+t[k].r)>>1;
if(l<=mid)
modify2(ls, l, r, val);
if(r>mid)
modify2(rs, l, r, val);
t[k].val = (t[ls].val+t[rs].val)%p;
}
ll ask(int k, int l, int r){
if(l<=t[k].l && t[k].r<=r)
return t[k].val;
spread(k);
int mid = (t[k].l+t[k].r)>>1;
ll res = 0;
if(l<=mid)
res = (res+ask(ls, l, r))%p;
if(r>mid)
res = (res+ask(rs, l, r))%p;
return res;
}
int main(){
freopen("input.txt", "r", stdin);
scanf("%d%d%lld", &n, &m, &p);
for(int i=1; i<=n; ++i)
scanf("%lld", s+i);
build(1, 1, n);
int a, x, y;
ll k;
for(int i=1; i<=m; ++i){
scanf("%d", &a);
if(a==1){
scanf("%d%d%lld", &x, &y, &k);
modify1(1, x, y, k);
}
if(a==2){
scanf("%d%d%lld", &x, &y, &k);
modify2(1, x, y, k);
}
if(a==3){
scanf("%d%d", &x, &y);
printf("%lld\n", ask(1, x, y));
}
}
return 0;
}