#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node {
int type, sz;
ll cost;
int inl, inr, outl, outr;
};
node nul = {0, 0, 0, 0, 0, 0, 0};
node merge(node &x, node &y) {
if (x.type == 0) return y;
if (y.type == 0) return x;
node ret;
ret.sz = x.sz + y.sz;
ret.type = max(x.type, y.type);
ret.cost = x.cost + y.cost;
if (x.type == 1 && y.type == 2) {
ret.outr = y.outr;
if (x.outr < y.inr) ret.inr = x.inr;
else if (x.outl > y.inr) ret.inr = x.inl, ret.cost += x.outl - y.inr;
else ret.inr = y.inr - x.sz;
} else if (x.type == 2 && y.type == 1) {
ret.inr = x.inr;
if (y.inl > x.outr) ret.outr = y.outl;
else if (y.inr < x.outr) ret.outr = y.outr, ret.cost += x.outr - y.inr;
else ret.outr = x.outr + y.sz;
} else if (x.type == 2 && y.type == 2) {
ret.inr = x.inr, ret.outr = y.outr;
ret.cost += max(x.outr - y.inr, (int)0);
} else if (x.type == 1 && y.type == 1) {
if (x.outr < y.inl) ret.type = 2, ret.inr = x.inr, ret.outr = y.outl;
else if (x.outl > y.inr) ret.type = 2, ret.inr = x.inl, ret.outr = y.outr, ret.cost += x.outl - y.inr;
else {
int l = max(x.outl, y.inl), r = min(x.outr, y.inr);
ret.inl = l - x.sz, ret.inr = r - x.sz;
ret.outl = l + y.sz, ret.outr = r + y.sz;
}
}
if (ret.type == 2) ret.inl = ret.inr, ret.outl = ret.outr;
return ret;
}
const int maxn = 3e5 + 5, maxN = 1.2e6 + 5;
int n;
pair<int,int> a[maxn];
int dir[2] = {1, -1};
node seg[maxN][2];
void build(int id, int l, int r, int i) {
// if (id != 0) cout << id << " " << l << " " << r << " " << i << endl;
if (l == r) {
// cout << l << " " << l * dir[i] << endl;
pair<int,int> cur = a[l * dir[i]];
seg[id][i] = {1, 1, 0, cur.first, cur.second, cur.first+1, cur.second+1};
return;
}
int mid = (l+r)/2;
if (i == 1) mid = (l+r-1)/2;
build(id*2, l, mid, i); build(id*2+1, mid+1, r, i);
seg[id][i] = merge(seg[id*2][i], seg[id*2+1][i]);
}
void update(int id, int l, int r, int target, int i) {
if (r < target || target < l) return;
if (l == r) {
pair<int,int> cur = a[l * dir[i]];
seg[id][i] = {1, 1, 0, cur.first, cur.second, cur.first+1, cur.second+1};
return;
}
int mid = (l+r)/2;
if (i == 1) mid = (l+r-1)/2;
update(id*2, l, mid, target, i); update(id*2+1, mid+1, r, target, i);
seg[id][i] = merge(seg[id*2][i], seg[id*2+1][i]);
}
node qry(int id, int l, int r, int findl, int findr, int i) {
if (r < findl || findr < l) return nul;
if (findl <= l && r <= findr) return seg[id][i];
int mid = (l+r)/2;
if (i == 1) mid = (l+r-1)/2;
node lhs = qry(id*2, l, mid, findl, findr, i);
node rhs = qry(id*2+1, mid+1, r, findl, findr, i);
return merge(lhs, rhs);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int q;
cin >> n >> q;
n--;
for (int i=1;i<=n;i++) {
cin >> a[i].first >> a[i].second;
a[i].second--;
}
// build(1, 1, n, 0);
// build(1, -n, -1, 1);
while (q--) {
int t;
cin >> t;
if (t == 1) {
int x, l, r;
cin >> x >> l >> r;
r--;
a[x] = {l, r};
update(1, 1, n, x, 0);
update(1, -n, -1, -x, 1);
} else if (t == 2) {
int l, intt, r, outt;
cin >> l >> intt >> r >> outt;
if (l == r) {
cout << max(intt - outt, (int)0) << "\n";
continue;
}
node cur = nul;
if (l < r) cur = qry(1, 1, n, l, r-1, 0);
else cur = qry(1, -n, -1, -(l-1), -r, 1);
cur = nul;
if (l < r) {
for (int i=l;i<=r-1;i++) {
node x = {1, 1, 0, a[i].first, a[i].second, a[i].first+1, a[i].second+1};
cur = merge(cur, x);
}
} else {
for (int i=l-1;i>=r;i--) {
node x = {1, 1, 0, a[i].first, a[i].second, a[i].first+1, a[i].second+1};
cur = merge(cur, x);
}
}
ll ans = cur.cost;
if (cur.type == 2) ans += max(intt - cur.inr, (int)0) + max(cur.outr - outt, (int)0);
else {
if (intt < cur.inl) intt = cur.inl;
else if (intt > cur.inr) ans += intt - cur.inr, intt = cur.inr;
intt += cur.sz;
ans += max(intt - outt, (int)0);
}
// cout << cur.type << " " << cur.inl << " " << cur.inr << " " << cur.sz << endl;
cout << ans << "\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... |