1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
| #include <bits/stdc++.h> #define son1 x*2 #define son2 x*2+1 using namespace std; const int INF = 0x3f3f3f3f; const int N = 10000000; typedef unsigned long long ll; ll n, m, ans, MOD; struct kuai { ll l, r, w, add, mul; }s[N]; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch<'0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar(); return s * w; } ll build(ll x, ll L, ll R) { s[x] = kuai{ L,R,0,0,1 }; if (L == R) return s[x].w = read() % MOD; ll mid = (L + R) >> 1; return s[x].w = (build(son1, L, mid) + build(son2, mid + 1, R)) % MOD; } void down(ll x) { s[son1].add = (s[x].add + s[son1].add * s[x].mul) % MOD; s[son2].add = (s[x].add + s[son2].add * s[x].mul) % MOD; s[son1].mul = (s[son1].mul * s[x].mul) % MOD; s[son2].mul = (s[son2].mul * s[x].mul) % MOD; s[son1].w = (s[son1].w * s[x].mul + s[x].add * (s[son1].r - s[son1].l + 1)) % MOD; s[son2].w = (s[son2].w * s[x].mul + s[x].add * (s[son2].r - s[son2].l + 1)) % MOD; s[x].add = 0; s[x].mul = 1; } ll ask(ll x, ll L, ll R) { down(x); if (s[x].l >= L && s[x].r <= R) return s[x].w % MOD; ll mid = (s[x].l + s[x].r) >> 1, ans = 0; if (L <= mid)ans += ask(son1, L, R); if (R > mid)ans += ask(son2, L, R); return ans % MOD; } void updata(ll x, ll w, ll typ, ll L, ll R) { down(x); if (typ == 1 && s[x].l >= L && s[x].r <= R) { s[x].mul = (s[x].mul * w) % MOD; s[x].add = (s[x].add * w) % MOD; s[x].w = (s[x].w * s[x].mul) % MOD; return; } if (typ == 2 && s[x].l >= L && s[x].r <= R) { s[x].add = (s[x].add + w) % MOD; s[x].w = (s[x].w + s[x].add * (s[x].r - s[x].l + 1)) % MOD; return; } ll mid = (s[x].l + s[x].r) >> 1; if (L <= mid)updata(son1, w, typ, L, R); if (R > mid)updata(son2, w, typ, L, R); s[x].w = s[son1].w + s[son2].w; } int main() { n = read(); MOD = read(); build(1, 1, n); m = read(); for (ll i = 1; i <= m; i++) { ll typ = read(), x = read(), y = read(); if (typ != 3)updata(1, read(), typ, x, y); else printf("%lld\n", ask(1, x, y)); } }
|