加强版双操作线段树

题目是洛谷的P3373，双操作加和乘。传送门点击即可获得屠龙宝刀

还是数组党的代码。

OK兄弟们，全体目光向我看齐，看我看我，我宣布个事，我是数组党，数组就是强

 1 #include 
 2 using namespace std;
 3 #define MAXN 1000005
 4 typedef long long ll;
 5 ll n, m, a[MAXN], ans[MAXN << 2], add[MAXN << 2], mul[MAXN << 2], x, y, k, oper, mod;
 6 inline ll ls(ll p) {
 7     return p << 1;
 8 }
 9 inline ll rs(ll p) {
10     return p << 1 | 1;
11 }
12 inline void push_up(ll p) {
13     ans[p] = (ans[ls(p)] + ans[rs(p)]) % mod;
14 }
15 void build(ll p, ll l, ll r) {
16     add[p] = 0;
17     mul[p] = 1;
18     if (l == r) {
19         ans[p] = a[l];
20         return;
21     }
22     ll mid = l + r >> 1;
23     build(ls(p), l, mid);
24     build(rs(p), mid + 1, r);
25     push_up(p);
26 }
27 inline void f(ll p, ll l, ll r,ll fa) {
28     mul[p] = (mul[p] * mul[fa]) % mod;
29     add[p] = (add[p] * mul[fa] + add[fa]) % mod;
30     ans[p] = (ans[p] * mul[fa] + add[fa] * (r - l + 1)) % mod;
31 }
32 inline void push_down(ll p, ll l, ll r) {
33     ll mid = (l + r) >> 1;
34     f(ls(p), l, mid, p);
35     f(rs(p), mid + 1, r, p);
36     mul[p] = 1;
37     add[p] = 0;
38 }
39 inline void update(ll dl, ll dr, ll l, ll r, ll p, ll k, bool op) {
40     if (dr < l || r < dl)return;
41     if (dl <= l && r <= dr) {
42         if (op == 1) { // do add
43             ans[p] = (ans[p] + k * (r - l + 1)) % mod;
44             add[p] = (add[p] + k) % mod;
45         }
46         else { // do multiply
47             ans[p] = (ans[p] * k) % mod;
48             mul[p] = (mul[p] * k) % mod;
49             add[p] = (add[p] * k) % mod;
50         }
51         return;
52     }
53     push_down(p, l, r);
54     ll mid = l + r >> 1;
55     if (dl <= mid)update(dl, dr, l, mid, ls(p), k, op);
56     if (mid < dr)update(dl, dr, mid + 1, r, rs(p), k, op);
57     push_up(p);
58 }
59 ll query(ll qx, ll qy, ll l, ll r, ll p) {
60     if (qy < l || r < qx)return 0;
61     if (qx <= l && r <= qy)return ans[p];
62     ll res = 0;
63     ll mid = l + r >> 1;
64     push_down(p, l, r);
65     if (qx <= mid)res += query(qx, qy, l, mid, ls(p));
66     if (qy > mid)res += query(qx, qy, mid + 1, r, rs(p));
67     return res % mod;
68 }
69 int main() {
70     scanf("%lld%lld%lld", &n, &m, &mod);
71     for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
72     build(1, 1, n);
73     while (m--) {
74         scanf("%lld", &oper);
75         switch (oper) {
76         case 1:
77             scanf("%lld%lld%lld", &x, &y, &k);
78             update(x, y, 1, n, 1, k, 0);
79             break;
80         case 2:
81             scanf("%lld%lld%lld", &x, &y, &k);
82             update(x, y, 1, n, 1, k, 1);
83             break;
84         default:
85             scanf("%lld%lld", &x, &y);
86             printf("%lld\n", query(x, y, 1, n, 1));
87         }
88     }
89     return 0;
90 }