AC

求点赞

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
using ll = long long;
struct Node {
ll l, r;
mutable ll A, B, start_t;
Node(ll l, ll r = 0, ll A = 0, ll B = 0, ll start_t = 0) :
l(l), r(r), A(A), B(B), start_t(start_t) {}
bool operator<(const Node& other) const {
return l < other.l;
}
};
set<Node> odt;
ll floor_sum(ll a, ll b, ll c, ll n) {
if (n < 0) return 0;
if (a == 0) {
return (b / c) * (n + 1);
}
if (a >= c || b >= c) {
return floor_sum(a % c, b % c, c, n) +
(a / c) * (n * (n + 1) / 2) +
(b / c) * (n + 1);
}
ll m = (a * n + b) / c;
return n * m - floor_sum(c, c - b - 1, a, m - 1);
}
ll range_sum(ll A, ll B, ll start_t, ll len) {
if (len <= 0) return 0;
if (B == 0) return 0;
ll sum_t = len * start_t + len * (len - 1) / 2;
ll part1 = A * sum_t;
ll sum_floor = floor_sum(A, 0, B, start_t + len - 1) - 
               floor_sum(A, 0, B, start_t - 1);
ll part2 = B * sum_floor;
return part1 - part2;
}
auto split(ll pos) {
auto it = odt.lower_bound(Node(pos));
if (it != odt.end() && it->l == pos) return it;
--it;
ll l = it->l, r = it->r, A = it->A, B = it->B, start_t = it->start_t;
odt.erase(it);
odt.insert(Node(l, pos - 1, A, B, start_t));
return odt.insert(Node(pos, r, A, B, start_t + (pos - l))).first;
}
void assign(ll l, ll r, ll A, ll B) {
auto itr = split(r + 1), itl = split(l);
odt.erase(itl, itr);
odt.insert(Node(l, r, A, B, 1));
}
ll query(ll l, ll r) {
auto itr = split(r + 1), itl = split(l);
ll res = 0;
for (auto it = itl; it != itr; ++it) {
ll len = it->r - it->l + 1;
if (it->B == 0) {
res += it->A * (it->start_t * len + len * (len - 1) / 2);
} else {
res += range_sum(it->A, it->B, it->start_t, len);
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll n, q;
cin >> n >> q;
odt.insert(Node(1, n, 0, 0, 0));
while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
        ll L, R, A, B;
        cin >> L >> R >> A >> B;
        assign(L, R, A, B);
    } else {
        ll L, R;
        cin >> L >> R;
        cout << query(L, R) << '\n';
    }
}

return 0;
}