@[suyulong1212](/user/275790)
终于可以AC了。问题不少。
```cpp
#include<bits/stdc++.h>
#define ll long long
#define maxn 100001
using namespace std;
int n, m, qq;
ll a[maxn], ans[maxn << 2], tagj[maxn << 2], tagc[maxn << 2];
inline int ls(int x){return x << 1;}
inline int rs(int x){return (x << 1) + 1;}
inline void push_up(int p){ans[p] = (ans[ls(p)] + ans[rs(p)]) % qq;}
void build(int left, int right, int p){
tagj[p] = 0, tagc[p] = 1;
if(left == right){
ans[p] = a[left] % qq;
return;
}
int mid = (left + right) >> 1;
build(left, mid, ls(p));
build(mid + 1, right, rs(p));
push_up(p);
}
inline void push_down(int l,int r,int p){
ll mid=(l+r)>>1;
tagc[p*2]*=tagc[p];
tagj[p*2]=tagj[p*2]*tagc[p]+tagj[p];
ans[p*2]=ans[p*2]*tagc[p]+(mid-l+1)*tagj[p];
tagc[p*2]%=qq,tagj[p*2]%=qq;ans[p*2]%=qq;
tagc[p*2+1]*=tagc[p];
tagj[p*2+1]=tagj[p*2+1]*tagc[p]+tagj[p];
ans[p*2+1]=ans[p*2+1]*tagc[p]+(r-mid)*tagj[p];
tagc[p*2+1]%=qq,tagj[p*2+1]%=qq;ans[p*2+1]%=qq;
tagj[p] = 0;
tagc[p] = 1;
}
inline void up_date(int nl, int nr, int l, int r, int p, int k, int info){
if(l>nr || r<nl) return;
if(l >= nl && r <= nr){
if(info == 1){
ans[p] *= k;
ans[p] %= qq;
tagj[p] *= k; tagj[p] %= qq;
tagc[p] *= k; tagc[p] %= qq;
if(tagc[p] == 0 && k) tagc[p] = qq;
}
else{
ans[p] += (r - l + 1) * k;
ans[p] %= qq;
tagj[p] += k; tagj[p] %= qq;
}
return;
}
push_down(l,r,p);
int mid = (l + r) >> 1;
up_date(nl, nr, l, mid, ls(p), k, info);
up_date(nl, nr, mid + 1, r, rs(p), k, info);
push_up(p);
}
inline ll query(int nl, int nr, int l, int r, int p){
if(l >= nl && r <= nr)
return ans[p] % qq;
if(l > nr || r < nl) return 0;
int mid = (l + r) >> 1;
push_down(l,r,p);
return (query(nl, nr, l, mid, ls(p)) + query(nl, nr, mid + 1, r, rs(p))) % qq;
}
int main(){
scanf("%d%d%d", &n, &m, &qq);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
build(1, n, 1);
while(m--){
int info, left, right, k;
scanf("%d", &info);
if(info == 3){
scanf("%d%d", &left, &right);
printf("%lld\n", query(left, right, 1, n, 1) % qq);
}
else{
scanf("%d%d%d", &left, &right, &k);
up_date(left, right, 1, n, 1, k % qq, info);
}
}
return 0;
}
```
by jwcub @ 2020-02-11 08:52:29
谢谢
by suyulong1212 @ 2020-02-11 09:20:24
Orz大佬爆切线段树
by xhQYm @ 2020-02-11 09:59:27