#include <bits/stdc++.h>
using namespace std;
#define type2 first.first
#define q2 first.second
#define x second.first
#define y second.second
#define l2 first.second
#define r2 second.first
typedef long long ll;
typedef pair<pair<int, ll>, pair<ll, ll>> detail;
pair<ll, ll> getP(detail &b, ll p) {
if (b.type2 == 0) {
if (p <= b.l2)
return {0, b.l2};
if (p <= b.r2)
return {0, p};
return {p - b.r2, b.r2};
}
return {b.x + max(0ll, p - b.q2), b.y};
}
const int N = 300'000;
int n, q, ids[4 * N + 10];
ll l[N + 10], r[N + 10];
detail seg[2][2 * N + 10];
pair<ll, ll> p[2][N + 10];
void readInput() {
cin >> n >> q;
for (int i = 1; i < n; i++)
cin >> l[i] >> r[i];
}
inline detail getDetail(int t, ll a, ll b, ll c = 0) {
detail res;
res = {{t, a}, {b, c}};
return res;
}
detail operator+(detail a, detail b) {
if (a.type2 == -1)
return b;
if (b.type2 == -1)
return a;
if (a.type2 == 0 && b.type2 == 1) {
if (a.r2 < b.q2)
return getDetail(1, a.r2, b.x, b.y);
if (a.l2 <= b.q2)
return getDetail(1, b.q2, b.x, b.y);
return getDetail(1, a.l2, getP(b, a.l2).first, b.y);
}
if (a.type2) {
pair<ll, ll> p = getP(b, a.y);
return getDetail(1, a.q2, a.x + p.first, p.second);
}
if (a.r2 <= b.l2)
return getDetail(1, a.r2, 0, b.l2);
if (b.r2 <= a.l2)
return getDetail(1, a.l2, getP(b, a.l2).first, b.r2);
return getDetail(0, max(a.l2, b.l2), min(a.r2, b.r2));
}
detail get(int t, int st, int en, int id = 1, int l = 1, int r = n) {
if (en <= l || r <= st)
return getDetail(-1, 0, 0);
if (st <= l && r <= en)
return seg[t][ids[id]];
int mid = (l + r) >> 1;
return get(t, st, en, id << 1, l, mid) + get(t, st, en, id << 1 | 1, mid, r);
}
void update(int t, int idx, pair<ll, ll> p, int id = 1, int l = 1, int r = n) {
if (idx < l || r <= idx)
return;
if (l + 1 == r) {
seg[t][ids[id]] = getDetail(0, p.first - l, p.second - l);
return;
}
int mid = (l + r) >> 1;
update(t, idx, p, id << 1, l, mid);
update(t, idx, p, id << 1 | 1, mid, r);
seg[t][ids[id]] = seg[t][ids[id << 1]] + seg[t][ids[id << 1 | 1]];
}
void build(int t, int id = 1, int l = 1, int r = n) {
if (l + 1 == r) {
seg[t][ids[id]] = getDetail(0, p[t][l].first - l, p[t][l].second - l);
return;
}
int mid = (l + r) >> 1;
build(t, id << 1, l, mid);
build(t, id << 1 | 1, mid, r);
seg[t][ids[id]] = seg[t][ids[id << 1]] + seg[t][ids[id << 1 | 1]];
}
int counter;
void calcIds(int id = 1, int l = 1, int r = n) {
ids[id] = ++counter;
if (l + 1 == r)
return;
int mid = (l + r) >> 1;
calcIds(id << 1, l, mid);
calcIds(id << 1 | 1, mid, r);
}
void build() {
calcIds();
for (int i = 1; i < n; i++)
p[0][i] = p[1][n - i] = {l[i], r[i] - 1};
build(0);
build(1);
}
void qeuryChange() {
ll p, l, r;
cin >> p >> l >> r;
update(0, p, {l, r - 1});
update(1, n - p + 1, {l, r - 1});
}
void queryGet() {
ll a, b, c, d;
cin >> a >> b >> c >> d;
if (a == c)
cout << max(0ll, b - d) << '\n';
else if (a < c) {
b -= a;
d -= c;
detail dt = get(0, a, c);
pair<ll, ll> p = getP(dt, b);
cout << p.first + max(0ll, p.second - d) << '\n';
}
else {
a = n - a + 1;
b -= a;
c = n - c + 1;
d -= c;
detail dt = get(1, a, c);
pair<ll, ll> p = getP(dt, b);
cout << p.first + max(0ll, p.second - d) << '\n';
}
}
void query() {
int type;
cin >> type;
if (type == 1)
qeuryChange();
else
queryGet();
}
void solve() {
while (q--)
query();
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
build();
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |