传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1798
注意，应保证当前节点维护的值是正确的，lazy tag只是一个下传标记，在下传时应即时更新儿子的维护值，在修改时也应即时更新当前节点的维护值。
#include <cstdio> const int maxn = 100005; int n, mod, a[maxn], m, t1, t2, t3, opr;
struct Node {
int ql, qr;
long long sm, mul, add;
} tree[maxn << 2]; inline void pushup(int p) {
tree[p].sm = (tree[p << 1].sm + tree[p << 1 | 1].sm) % mod;
}
inline void pushdown(int p) {
tree[p << 1].mul = tree[p << 1].mul * tree[p].mul % mod;
tree[p << 1].add = (tree[p << 1].add * tree[p].mul + tree[p].add) % mod;
tree[p << 1].sm = (tree[p << 1].sm * tree[p].mul + tree[p].add * (tree[p << 1].qr - tree[p << 1].ql + 1)) % mod; tree[p << 1 | 1].mul = tree[p << 1 | 1].mul * tree[p].mul % mod;
tree[p << 1 | 1].add = (tree[p << 1 | 1].add * tree[p].mul + tree[p].add) % mod;
tree[p << 1 | 1].sm = (tree[p << 1 | 1].sm * tree[p].mul + tree[p].add * (tree[p << 1 | 1].qr - tree[p << 1 | 1].ql + 1)) % mod; tree[p].mul = 1;
tree[p].add = 0;
}
void make_tree(int p, int left, int right) {
tree[p].ql = left;
tree[p].qr = right;
tree[p].mul = 1;
if (left == right) {
tree[p].sm = (long long)(a[left] % mod);
return;
}
int mid = (left + right) >> 1;
make_tree(p << 1, left, mid);
make_tree(p << 1 | 1, mid + 1, right);
pushup(p);
}
void mull(int p, int left, int right, int c) {
if (tree[p].ql == left && tree[p].qr == right) {
tree[p].mul = tree[p].mul * (long long)c % mod;
tree[p].add = tree[p].add * (long long)c % mod;
tree[p].sm = tree[p].sm * (long long)c % mod;
return;
}
pushdown(p);
int mid = (tree[p].ql + tree[p].qr) >> 1;
if (right <= mid) {
mull(p << 1, left, right, c);
}
else if (left > mid) {
mull(p << 1 | 1, left, right, c);
}
else {
mull(p << 1, left, mid, c);
mull(p << 1 | 1, mid + 1, right, c);
}
pushup(p);
}
void addd(int p, int left, int right, int c) {
if (tree[p].ql == left && tree[p].qr == right) {
tree[p].add = (tree[p].add + (long long)c) % mod;
tree[p].sm = (tree[p].sm + (long long)c * (long long)(tree[p].qr - tree[p].ql + 1)) % mod;
return;
}
pushdown(p);
int mid = (tree[p].ql + tree[p].qr) >> 1;
if (right <= mid) {
addd(p << 1, left, right, c);
}
else if (left > mid) {
addd(p << 1 | 1, left, right, c);
}
else {
addd(p << 1, left, mid, c);
addd(p << 1 | 1, mid + 1, right, c);
}
pushup(p);
}
int qry(int p, int left, int right) {
if (tree[p].ql == left && tree[p].qr == right) {
return (int)tree[p].sm;
}
pushdown(p);
int mid = (tree[p].ql + tree[p].qr) >> 1, rt;
if (right <= mid) {
rt = qry(p << 1, left, right);
}
else if (left > mid) {
rt = qry(p << 1 | 1, left, right);
}
else {
rt = qry(p << 1, left, mid);
rt = (rt + qry(p << 1 | 1, mid + 1, right)) % mod;
}
pushup(p);
return rt;
} int main(void) {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d%d", &n, &mod);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
make_tree(1, 1, n);
scanf("%d", &m);
while (m--) {
scanf("%d%d%d", &opr, &t1, &t2);
if (opr == 1) {
scanf("%d", &t3);
mull(1, t1, t2, t3);
}
else if (opr == 2) {
scanf("%d", &t3);
addd(1, t1, t2, t3);
}
else {
printf("%d\n", qry(1, t1, t2));
}
}
return 0;
}