#include <bits/stdc++.h>
typedef long long ll;
const ll inf = 1e15;
struct Query {
ll a, b, c, d;
int i, t;
};
template <typename T> class SegmentTree {
public:
std::vector<T> seg;
int n;
std::function<T(T, T)> f = [](T a, T b) { return a + b; };
T idt;
SegmentTree(int n) : n(n), idt(0) { seg.resize(2 * n, idt); }
SegmentTree(int n, const std::function<T(T, T)> &f, T idt)
: n(n), f(f), idt(idt) {
seg.resize(2 * n, idt);
}
void set(int idx, T x) {
for (seg[idx += n] = x, idx /= 2; idx > 0; idx /= 2) {
seg[idx] = f(seg[2 * idx], seg[2 * idx + 1]);
}
}
T query(int l, int r) {
T ansL = idt, ansR = idt;
for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
if (l & 1) {
ansL = f(ansL, seg[l++]);
}
if (r & 1) {
ansR = f(seg[--r], ansR);
}
}
return f(ansL, ansR);
}
};
void solve(int n, int q, std::vector<ll> l, std::vector<ll> r,
std::vector<Query> queries, std::vector<ll> &ans) {
for (int i = 0; i < n - 1; ++i) {
l[i] -= i, r[i] -= i + 1;
}
struct Function {
bool type;
ll l, r, k;
std::pair<ll, ll> operator()(ll t) {
if (!type) {
if (t <= r) {
return {std::max(l, t), 0};
}
return {r, t - r};
} else {
return {r, std::max(0LL, t - l) + k};
}
}
};
auto f = [&](Function x, Function y) -> Function {
if (!x.type and !y.type) {
ll l = std::max(x.l, y.l), r = std::min(x.r, y.r);
if (l <= r) {
return {0, l, r, 0};
}
if (x.l > y.r) {
return {1, x.l, y.r, x.l - y.r};
}
return {1, x.r, y.l, 0};
}
if (!x.type and y.type) {
ll r = std::min(x.r, y.l);
if (x.l <= r) {
return {1, r, y.r, y.k};
}
return {1, x.l, y.r, y.k + x.l - r};
}
auto [t, c] = y(x.r);
return {1, x.l, t, x.k + c};
};
SegmentTree<Function> tree(n - 1, f, {0, -inf, inf, 0});
for (int i = 0; i < n - 1; ++i) {
tree.set(i, {0, l[i], r[i], 0});
}
for (auto &[a, b, c, d, i, t] : queries) {
if (t == 1) {
tree.set(a, {0, b - a, c - a - 1, 0});
} else {
b -= a, d -= c;
auto [time, cost] = tree.query(a, c - 1)(b);
ans[i] = std::max(ans[i], cost + std::max(0LL, time - d));
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<ll> l(n - 1), r(n - 1);
for (int i = 0; i < n - 1; ++i) {
std::cin >> l[i] >> r[i];
}
std::vector<ll> ans(q);
std::vector<Query> q1, q2;
int j = 0;
for (int i = 0, t; i < q; ++i) {
ll a, b, c, d;
std::cin >> t;
if (t == 1) {
std::cin >> a >> b >> c;
--a;
q1.push_back({a, b, c, 0, 0, 1});
q2.push_back({n - a - 2, b, c, 0, 0, 1});
} else {
std::cin >> a >> b >> c >> d;
--a, --c;
if (a == c) {
ans[j++] = std::max(0LL, b - d);
continue;
}
if (a < c) {
q1.push_back({a, b, c, d, j, 2});
} else {
q2.push_back({n - a - 1, b, n - c - 1, d, j, 2});
}
j++;
}
}
solve(n, q, l, r, q1, ans);
std::reverse(l.begin(), l.end());
std::reverse(r.begin(), r.end());
solve(n, q, l, r, q2, ans);
for (int i = 0; i < j; ++i) {
std::cout << ans[i] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |