#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int32_t l, r;
int x, st, out;
char rng;
};
const int N = 3e5 + 10;
int n, q;
node tree1[4*N], tree2[4*N], ans, tmp;
pair<int,int> inps[N];
void upd(node &v,node &u1,node &u2) {
if (u1.rng && u2.rng) {
if (min(u1.r,u2.r) >= max(u1.l,u2.l)) {
v.rng = 1;
v.l = max(u1.l,u2.l);
v.r = min(u1.r,u2.r);
} else {
v.rng = 0;
if (u1.l > u2.r) {
v.x = u1.l-u2.r;
v.st = u1.l;
v.out = u2.r;
} else {
v.x = 0;
v.st = u1.r;
v.out = u2.l;
}
}
}
if (u1.rng && !u2.rng) {
v.rng = 0;
v.out = u2.out;
v.x = u2.x+max(0,u1.l-u2.st);
v.st = max(u1.l,min(u1.r,u2.st));
}
if (!u1.rng && u2.rng) {
v = u1;
if (u1.out > u2.r) {
v.out = u2.r;
v.x += u1.out - u2.r;
} else if (u1.out < u2.l) {
v.out = u2.l;
}
}
if (!u1.rng && !u2.rng) {
v = u1;
v.out = u2.out;
v.x += u2.x+max(0,u1.out-u2.st);
}
}
void build(int v,int tl,int tr) {
if (tl == tr) {
tree1[v].rng = 1;
tree1[v].l = inps[tl].first-tl;
tree1[v].r = inps[tl].second-tl-1;
tree2[v].rng = 1;
tree2[v].l = inps[tl].first-(n-tl);
tree2[v].r = inps[tl].second-(n-tl)-1;
return;
}
int mid = (tl+tr)/2;
build(2*v,tl,mid);
build(2*v+1,mid+1,tr);
upd(tree1[v],tree1[2*v],tree1[2*v+1]);
upd(tree2[v],tree2[2*v+1],tree2[2*v]);
}
void change(int v,int tl,int tr,int ind) {
if (ind > tr || ind < tl) return;
if (tl == tr) {
tree1[v].rng = 1;
tree1[v].l = inps[tl].first-tl;
tree1[v].r = inps[tl].second-tl-1;
tree2[v].rng = 1;
tree2[v].l = inps[tl].first-(n-tl);
tree2[v].r = inps[tl].second-(n-tl)-1;
return;
}
int mid = (tl+tr)/2;
change(2*v,tl,mid,ind);
change(2*v+1,mid+1,tr,ind);
upd(tree1[v],tree1[2*v],tree1[2*v+1]);
upd(tree2[v],tree2[2*v+1],tree2[2*v]);
}
void GET(int v,int tl,int tr,int l,int r,int id) {
if (r < l) return;
if (tl == l && tr == r) {
tmp = ans;
if (id == 1) {
upd(ans,tmp,tree1[v]);
} else {
upd(ans,tmp,tree2[v]);
}
return;
}
int mid = (tl+tr)/2;
if (id == 1) {
GET(2*v,tl,mid,l,min(r,mid),id);
GET(2*v+1,mid+1,tr,max(l,mid+1),r,id);
} else {
GET(2*v+1,mid+1,tr,max(l,mid+1),r,id);
GET(2*v,tl,mid,l,min(r,mid),id);
}
}
/*
5 5
3 5
4 8
2 6
5 10
2 5 3 1 10
2 2 6 5 6
1 3 4 6
2 3 3 4 3
2 4 5 1 5
*/
void solve() {
cin >> n >> q;
for (int i = 1;i <= n-1;i++) {
cin >> inps[i].first >> inps[i].second;
}
build(1,1,n-1);
for (int i = 0;i < q;i++) {
int t;
cin >> t;
if (t == 1) {
int p, s, e;
cin >> p >> s >> e;
inps[p] = {s,e};
change(1,1,n-1,p);
} else {
int a, b, c, d;
cin >> a >> b >> c >> d;
if (a == c) {
cout << max(0ll,b-d) << '\n';
continue;
}
ans.rng = 1;
ans.l = -21e8;
ans.r = 21e8;
if (a < c) {
b -= a;
d -= c;
GET(1,1,n-1,a,c-1,1);
} else {
b -= (n-a+1);
d -= (n-c+1);
GET(1,1,n-1,c,a-1,2);
}
//cout << "a,b,c,d = " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
//cout << "ans.rng,l,r,x,st,out = " << ans.rng << ' ' << ans.l << ' ' << ans.r << ' ' << ans.x << ' ' << ans.st << ' ' << ans.out << '\n';
int cost = 0, loc;
if (ans.rng) {
cost = max(0ll,b-ans.r);
loc = b;
if (loc < ans.l) loc = ans.l;
if (loc > ans.r) loc = ans.r;
} else {
cost = ans.x+max(0ll,b-ans.st);
loc = ans.out;
}
cout << cost + max(0ll,loc-d) << '\n';
}
}
}
/*
5 1
3 5
4 8
2 6
5 10
2 5 3 1 10
*/
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
컴파일 시 표준 에러 (stderr) 메시지
timeleap.cpp: In function 'void upd(node&, node&, node&)':
timeleap.cpp:38:23: error: no matching function for call to 'max(int, long long int)'
38 | v.x = u2.x+max(0,u1.l-u2.st);
| ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from timeleap.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
257 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: template argument deduction/substitution failed:
timeleap.cpp:38:23: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
38 | v.x = u2.x+max(0,u1.l-u2.st);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: template argument deduction/substitution failed:
timeleap.cpp:38:23: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
38 | v.x = u2.x+max(0,u1.l-u2.st);
| ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
5795 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: template argument deduction/substitution failed:
timeleap.cpp:38:23: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
38 | v.x = u2.x+max(0,u1.l-u2.st);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
5805 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: template argument deduction/substitution failed:
timeleap.cpp:38:23: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
38 | v.x = u2.x+max(0,u1.l-u2.st);
| ~~~^~~~~~~~~~~~~~
timeleap.cpp:39:28: error: no matching function for call to 'min(int32_t&, long long int&)'
39 | v.st = max(u1.l,min(u1.r,u2.st));
| ~~~^~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
233 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: template argument deduction/substitution failed:
timeleap.cpp:39:28: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
39 | v.st = max(u1.l,min(u1.r,u2.st));
| ~~~^~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
281 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: template argument deduction/substitution failed:
timeleap.cpp:39:28: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
39 | v.st = max(u1.l,min(u1.r,u2.st));
| ~~~^~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
5775 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: template argument deduction/substitution failed:
timeleap.cpp:39:28: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
39 | v.st = max(u1.l,min(u1.r,u2.st));
| ~~~^~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
5785 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: template argument deduction/substitution failed:
timeleap.cpp:39:28: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
39 | v.st = max(u1.l,min(u1.r,u2.st));
| ~~~^~~~~~~~~~~~
timeleap.cpp:53:24: error: no matching function for call to 'max(int, long long int)'
53 | v.x += u2.x+max(0,u1.out-u2.st);
| ~~~^~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
257 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: template argument deduction/substitution failed:
timeleap.cpp:53:24: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
53 | v.x += u2.x+max(0,u1.out-u2.st);
| ~~~^~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: template argument deduction/substitution failed:
timeleap.cpp:53:24: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
53 | v.x += u2.x+max(0,u1.out-u2.st);
| ~~~^~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
5795 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: template argument deduction/substitution failed:
timeleap.cpp:53:24: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
53 | v.x += u2.x+max(0,u1.out-u2.st);
| ~~~^~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
5805 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: template argument deduction/substitution failed:
timeleap.cpp:53:24: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
53 | v.x += u2.x+max(0,u1.out-u2.st);
| ~~~^~~~~~~~~~~~~~~~