线段树优化代码示例 - 使用lazytag实现高效区间操作

#include <bits/stdc++.h> using namespace std; typedef long long ll;

const int N = 100007; const int MOD = 1e9 + 7;

int p; ll a[N]; ll st[4 * N], mul[4 * N], add[4 * N];

void build(int root, int l, int r) { mul[root] = 1; add[root] = 0; if (l == r) { st[root] = a[l]; } else { int m = (l + r) / 2; build(root * 2, l, m); build(root * 2 + 1, m + 1, r); st[root] = (st[root * 2] + st[root * 2 + 1]) % p; } st[root] %= p; return; }

void pushdown(int root, int l, int r) { int m = (l + r) / 2; st[root * 2] = (st[root * 2] * mul[root] + add[root] * (m - l + 1)) % p; st[root * 2 + 1] = (st[root * 2 + 1] * mul[root] + add[root] * (r - m)) % p; mul[root * 2] = (mul[root * 2] * mul[root]) % p; mul[root * 2 + 1] = (mul[root * 2 + 1] * mul[root]) % p; add[root * 2] = (add[root * 2] * mul[root] + add[root]) % p; add[root * 2 + 1] = (add[root * 2 + 1] * mul[root] + add[root]) % p; mul[root] = 1; add[root] = 0; return; }

void update1(int root, int stdl, int stdr, int l, int r, ll k) { if (r < stdl || stdr < l) { return; } if (l <= stdl && stdr <= r) { st[root] = (st[root] * k) % p; mul[root] = (mul[root] * k) % p; add[root] = (add[root] * k) % p; return; } pushdown(root, stdl, stdr); int m = (stdl + stdr) / 2; update1(root * 2, stdl, m, l, r, k); update1(root * 2 + 1, m + 1, stdr, l, r, k); st[root] = (st[root * 2] + st[root * 2 + 1]) % p; return; }

void update2(int root, int stdl, int stdr, int l, int r, ll k) { if (r < stdl || stdr < l) { return; } if (l <= stdl && stdr <= r) { add[root] = (add[root] + k) % p; st[root] = (st[root] + k * (stdr - stdl + 1)) % p; return; } pushdown(root, stdl, stdr); int m = (stdl + stdr) / 2; update2(root * 2, stdl, m, l, r, k); update2(root * 2 + 1, m + 1, stdr, l, r, k); st[root] = (st[root * 2] + st[root * 2 + 1]) % p; return; }

ll query(int root, int stdl, int stdr, int l, int r) { if (r < stdl || stdr < l) { return 0; } if (l <= stdl && stdr <= r) { return st[root]; } pushdown(root, stdl, stdr); int m = (stdl + stdr) / 2; return (query(root * 2, stdl, m, l, r) + query(root * 2 + 1, m + 1, stdr, l, r)) % p; }

int main() { int n, m; scanf("%d%d%d", &n, &m, &p); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } build(1, 1, n); while (m--) { int chk; scanf("%d", &chk); int x, y; ll k; if (chk == 1) { scanf("%d%d%lld", &x, &y, &k); update1(1, 1, n, x, y, k); } else if (chk == 2) { scanf("%d%d%lld", &x, &y, &k); update2(1, 1, n, x, y, k); } else { scanf("%d%d", &x, &y); printf("%lld\n", query(1, 1, n, x, y)); } } return 0; }