```cpp
#include <iostream>
using namespace std;
typedef long long ll;
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
const int maxn = 100000 + 5;
struct Node
{
ll v, mul, add;
Node()
{
v = 0;
mul = 1;
add = 0;
}
} ans[maxn << 2];
ll n, m, mod;
ll a[maxn];
inline void push_up(ll p)
{
ans[p].v = (ans[lc(p)].v + ans[rc(p)].v) % mod;
}
inline void build(ll l, ll r, ll p)
{
if (l == r)
ans[p].v = a[l];
else
{
ll mid = (l + r) >> 1;
build(l, mid, lc(p));
build(mid + 1, r, rc(p));
push_up(p);
}
ans[p].v = ans[p].v % mod;
}
inline void push_down(ll l, ll r, ll p)
{
if (ans[p].mul == 1 && ans[p].add == 0)
return;
ll mid = (l + r) >> 1;
ll lp = lc(p);
ll rp = rc(p);
ll mul = ans[p].mul;
ll add = ans[p].add;
ans[lp].v = (ans[lp].v * mul + add * (mid - l + 1)) % mod;
ans[rp].v = (ans[rp].v * mul + add * (r - mid)) % mod;
// update
ans[lp].mul *= mul % mod;
ans[rp].mul *= mul % mod;
ans[lp].add += add % mod;
ans[rp].add += add % mod;
// reset
ans[p].mul = 1;
ans[p].add = 0;
}
inline void update_add(ll l, ll r, ll p, ll k, ll nl, ll nr)
{
if (nr < l || r < nl)
return;
if (l <= nl && nr <= r)
{
ans[p].v += k * (nr - nl + 1);
ans[p].add += k;
}
else
{
push_down(nl, nr, p);
ll mid = (nl + nr) >> 1;
update_add(l, r, lc(p), k, nl, mid);
update_add(l, r, rc(p), k, mid + 1, nr);
push_up(p);
}
}
inline void update_mul(ll l, ll r, ll p, ll k, ll nl, ll nr)
{
if (nr < l || r < nl)
return;
if (l <= nl && nr <= r)
{
ans[p].v *= k;
ans[p].mul *= k;
}
else
{
push_down(nl, nr, p);
ll mid = (nl + nr) >> 1;
update_mul(l, r, lc(p), k, nl, mid);
update_mul(l, r, rc(p), k, mid + 1, nr);
push_up(p);
}
}
inline ll query(ll l, ll r, ll p, ll nl, ll nr)
{
if (l <= nl && nr <= r)
return ans[p].v % mod;
ll shit = 0;
ll mid = (nl + nr) >> 1;
if (nl<=mid)
shit += query(l, r, lc(p), nl, mid);
if (nr > mid)
shit += query(l, r, rc(p), mid + 1, nr);
return shit % mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> mod;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, n, 1);
while (m--)
{
ll a1;
ll _x, _y, _k;
cin >> a1;
if (a1 == 1)
{
cin >> _x >> _y >> _k;
update_mul(1, n, 1, _k, _x, _y);
}
else if (a1 == 2)
{
cin >> _x >> _y >> _k;
update_add(1, n, 1, _k, _x, _y);
}
else
{
cin >> _x >> _y;
cout << query(1, n, 1, _x, _y) << endl;
}
}
return 0;
}
```
by 扩散性百万甜面包 @ 2018-02-22 21:15:43
下传时加法标记需要乘以乘法标记。
另外，线段树建议重写。
by EternalAlexander @ 2018-02-22 21:28:49
@[EternalAlexander](/space/show?uid=48355) 捕捉大佬一只
by Clever_Jimmy @ 2018-02-22 22:07:17
@[Himself65](/space/show?uid=72813) 这里是面包姐姐的黑历史吗？
by memset0 @ 2018-07-10 18:10:31
@[memset0](/space/show?uid=53495) 对不起，刚学编程
by 扩散性百万甜面包 @ 2018-07-10 18:18:31