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 82 83 84 85 86 87 88 89 90 91 92 93
| #include <bits/stdc++.h> #define fl first #define fr second #define pb push_back #define mp make_pair using namespace std;
typedef long long LL; typedef pair<int, int> pii; const int N = 100000 + 5;
struct Node { LL l, r; mutable LL v, a, b, q; Node(const LL &l, const LL &r, const LL &v, const LL &a, const LL &b) : l(l), r(r), v(v), a(a), b(b) {} inline bool operator < (const Node &o) const { return l < o.l; } };
typedef set<Node>::iterator iter;
int n, m; set<Node> odt;
iter split(LL x) { if (x > n) return odt.end(); iter it = --odt.upper_bound(Node{x, 0, 0, 0, 0}); if (it->l == x) return it; LL l = it->l, r = it->r; LL v = it->v, a = it->a, b = it->b; odt.erase(it); odt.insert(Node(l, x - 1, v, a, b)); return odt.insert(Node(x, r, ((v + x - l) % b + b) % b, a, b)).first; }
void assign(LL l, LL r, LL v, LL a, LL b) { iter itr = split(r + 1), itl = split(l); odt.erase(itl, itr); odt.insert(Node(l, r, v, a, b)); }
LL f(LL a, LL b, LL c, LL n) { if (!a) return (b / c) * (n + 1); if (a >= c || b >= c) { return f(a % c, b % c, c, n) + (n * (n + 1) / 2) * (a / c) + (n + 1) * (b / c); } LL m = (a * n + b) / c; return n * m - f(c, c - b - 1, a, m - 1); }
inline LL Get(LL v, LL a, LL b) { return v * (v + 1) / 2 * a - b * f(a, 0, b, v); }
LL Query(LL l, LL r) { iter itr = split(r + 1), itl = split(l); LL res = 0; for (; itl != itr; ++itl) { res += Get(itl->v + itl->r - itl->l, itl->a, itl->b); res -= Get(itl->v - 1, itl->a, itl->b); } return res; }
int main() { scanf("%d%d", &n, &m); odt.insert(Node{1, n, 0, 0, 1}); while (m--) { int opt, l, r, a, b; scanf("%d", &opt); if (opt == 1) { scanf("%d%d%d%d", &l, &r, &a, &b); assign(l, r, 1, a, b); } else { scanf("%d%d", &l, &r); printf("%lld\n", Query(l, r)); } } return 0; }
|