原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1798
线段树区间更新：
1. 区间同同时加上一个数
2. 区间同时乘以一个数
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define lc root<<1
#define rc root<<1|1
typedef unsigned long long ull;
const int Max_N = ;
int Mod;
struct Node {
ull sum, add, mul;
};
struct SegTree {
Node seg[Max_N << ];
inline void push_up(int root) {
seg[root].sum = (seg[lc].sum + seg[rc].sum) % Mod;
}
inline void built(int root, int l, int r) {
seg[root].add = , seg[root].mul = ;
if (l == r) {
scanf("%lld", &seg[root].sum);
seg[root].sum %= Mod;
return;
}
int mid = (l + r) >> ;
built(lc, l, mid);
built(rc, mid + , r);
push_up(root);
}
inline void push_down(int root, int len) {
if (seg[root].add != || seg[root].mul != ) {
ull &_add = seg[root].add, &_mul = seg[root].mul;
seg[lc].sum = (seg[lc].sum * _mul + (len - (len >> )) * _add) % Mod;
seg[lc].mul = (seg[lc].mul * _mul) % Mod;
seg[lc].add = (seg[lc].add * _mul + _add) % Mod;
seg[rc].sum = (seg[rc].sum * _mul + (len >> ) * _add) % Mod;
seg[rc].mul = (seg[rc].mul * _mul) % Mod;
seg[rc].add = (seg[rc].add * _mul + _add) % Mod;
_add = , _mul = ;
}
}
inline void update(int root, int l, int r, int x, int y, ull val, ull mul) {
if (x > r || y < l) return;
if (x <= l && y >= r) {
seg[root].add = (seg[root].add * mul + val) % Mod;
seg[root].mul = (seg[root].mul * mul) % Mod;
seg[root].sum = (seg[root].sum * mul + val * (r - l + )) % Mod;
return;
}
push_down(root, r - l + );
int mid = (l + r) >> ;
update(lc, l, mid, x, y, val, mul);
update(rc, mid + , r, x, y, val, mul);
push_up(root);
}
inline ull query(int root, int l, int r, int x, int y) {
if (x > r || y < l) return ;
if (x <= l && y >= r) {
return seg[root].sum;
}
push_down(root, r - l + );
ull ret = ;
int mid = (l + r) >> ;
ret += query(lc, l, mid, x, y);
ret += query(rc, mid + , r, x, y);
return ret %= Mod;
}
}seg;
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
int n, m, a, b, c, d;
while (~scanf("%d %d", &n, &Mod)) {
seg.built(, , n);
scanf("%d", &m);
while (m--) {
scanf("%d", &a);
if ( == a) {
scanf("%d %d %d", &b, &c, &d);
seg.update(, , n, b, c, , d);
} else if ( == a) {
scanf("%d %d %d", &b, &c, &d);
seg.update(, , n, b, c, d, );
} else {
scanf("%d %d", &b, &c);
printf("%lld\n", seg.query(, , n, b, c));
}
}
}
return ;
}