第一行包含三个整数 n,m,pn,m,pn,m,p，分别表示该数列数字的个数、操作的总个数和模数。 第二行包含 nnn 个用空格分隔的整数，其中第 iii 个数字表示数列第 iii 项的初始值。 接下来 mmm 行每行包含若干个整数，表示一个操作，具体如下： 操作 111： 格式：1 x y k 含义：将区间 [x,y][x,y][x,y] 内每个数乘上 kkk 操作 222： 格式：2 x y k 含义：将区间 [x,y][x,y][x,y] 内每个数加上 kkk 操作 333： 格式：3 x y 含义：输出区间 [x,y][x,y][x,y] 内每个数的和对 ppp 取模所得的结果
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 2e5 + 10; int tot = 0; int n, m; ll p; struct node { int l, r; ll sum, add, mul; node() {l = r = sum = add = 0; mul = 1;}; }tree[N * 4]; inline int ls(int cur) { return cur << 1; } inline int rs (int cur) { return (cur << 1) | 1; } inline void push_up(int cur) { tree[cur].sum = (tree[ls(cur)].sum + tree[rs(cur)].sum) % p; } inline void push_down(int cur) { if (tree[cur].mul != 1 or tree[cur].add != 0) { tree[ls(cur)].sum = (tree[ls(cur)].sum * tree[cur].mul + (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].add) % p; tree[rs(cur)].sum = (tree[rs(cur)].sum * tree[cur].mul + (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].add) % p; tree[ls(cur)].mul = tree[ls(cur)].mul * tree[cur].mul % p; tree[rs(cur)].mul = tree[rs(cur)].mul * tree[cur].mul % p; tree[ls(cur)].add = (tree[ls(cur)].add * tree[cur].mul + tree[cur].add) % p; tree[rs(cur)].add = (tree[rs(cur)].add * tree[cur].mul + tree[cur].add) % p; tree[cur].add = 0; tree[cur].mul = 1; } } void build(int cur, int l, int r) { if (l == r) { ll a; scanf("%lld", &a); tree[cur].sum = a; tree[cur].l = l; tree[cur].r = r; return; } int mid = (l + r) >> 1; tree[cur].l = l; tree[cur].r = r; build(ls(cur), l, mid); build(rs(cur), mid + 1, r); push_up(cur); } void add(int cur, int l, int r, int v) { if (tree[cur].l == l and tree[cur].r == r){ tree[cur].sum = (tree[cur].sum + (r - l + 1) * v) %p; tree[cur].add = (tree[cur].add + v) % p; return; } push_down(cur); //继续往下 //更新接下来的区间，保证他们是最新的 int mid = (tree[cur].l + tree[cur].r) >> 1; if (r <= mid) { add(ls(cur), l, r, v); } else if (l > mid) { add(rs(cur), l, r, v); } else { add(ls(cur), l, mid, v); add(rs(cur), mid + 1, r, v); } //所有区间都从自己的子区间获取值的更新 push_up(cur); } void mul(int cur, int l, int r, int v) { if (tree[cur].l == l and tree[cur].r == r){ tree[cur].sum = (tree[cur].sum * v) % p; tree[cur].mul = (tree[cur].mul * v) % p; tree[cur].add = (tree[cur].add * v) % p; return; } push_down(cur); int mid = (tree[cur].l + tree[cur].r) >> 1; if (r <= mid) { mul(ls(cur), l, r, v); } else if (l > mid) { mul(rs(cur), l, r, v); } else { mul(ls(cur), l, mid, v); mul(rs(cur), mid + 1, r, v); } //所有区间都从自己的子区间获取值的更新 push_up(cur); } ll query(int cur, int l, int r) { if (tree[cur].l == l and tree[cur].r == r){ return tree[cur].sum; } push_down(cur); int mid = (tree[cur].l + tree[cur].r) >> 1; if (r <= mid) { return query(ls(cur), l, r); } else if (l > mid) { return query(rs(cur), l, r); } else { return (query(ls(cur), l, mid) + query(rs(cur), mid + 1, r)) % p; } //没有更新操作，所以不需要push_up } int main() { #ifndef ONLINE_JUDGE freopen("D:/VS CODE/C++/in.txt", "r", stdin); freopen("D:/VS CODE/C++/out.txt", "w", stdout); #endif cin >> n >> m >> p; build(1, 1, n); while (m--) { int o, x, y, k; scanf("%d", &o); if (o == 1) { cin >> x >> y >> k; mul(1, x, y, k); } else if (o == 2) { cin >> x >> y >> k; add(1, x, y, k); } else { cin >> x >> y; cout << query(1, x, y) << endl; } } fclose(stdin); fclose(stdout); return 0; }