//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
struct node{
ll s1,s2,e1,e2,c1,c2,sz;
};
const int mxn=3e5+5;
vector<vector<node>> segtree(2,vector<node>(mxn*4));
int n,q;
ll L[mxn],R[mxn];
node trash;
node merge(node a,node b){
if(a.sz==-1) return b;
if(b.sz==-1) return a;
node ans;
ans.sz=a.sz+b.sz;
ans.s1=a.s1;
ans.s2=a.s2;
{
ans.c1=a.c1;
if(a.e1>b.s1){
ans.c1+=b.c1+(a.e1-b.s1);
ans.e1=b.e1;
}
else if(a.e1>=b.s2){
int dif=b.c1-b.c2;
ans.c1+=b.c2+max(0ll,dif-(b.s1-a.e1));
int res=a.e1+b.sz;
if(res>b.e1){
ans.e1=b.e1;
}
else{
ans.e1=max(res,b.e2);
}
}
else{
ans.c1+=b.c2;
ans.e1=b.e2;
}
}
{
ans.c2=a.c2;
if(a.e2>b.s1){
ans.c2+=b.c1+(a.e2-b.s1);
ans.e2=b.e1;
}
else if(a.e2>=b.s2){
int dif=b.c1-b.c2;
ans.c2+=b.c2+max(0ll,dif-(b.s1-a.e2));
int res=a.e2+b.sz;
if(res>b.e1){
ans.e2=b.e1;
}
else{
ans.e2=max(res,b.e2);
}
}
else{
ans.c2+=b.c2;
ans.e2=b.e2;
}
}
return ans;
}
void build(int id,int l=1,int r=n-1,int v=1){
if(l==r){
segtree[id][v].s1=R[l]-1;
segtree[id][v].s2=L[l];
segtree[id][v].e1=R[l];
segtree[id][v].e2=L[l]+1;
segtree[id][v].c1=segtree[id][v].c2=0;
segtree[id][v].sz=1;
return;
}
int mid=(l+r)/2;
build(id,l,mid,v*2);
build(id,mid+1,r,v*2+1);
segtree[id][v]=merge(segtree[id][v*2],segtree[id][v*2+1]);
}
void update(int id,int pos,int s,int e,int l=1,int r=n-1,int v=1){
if(l==r){
segtree[id][v].s1=e-1;
segtree[id][v].s2=s;
segtree[id][v].e1=e;
segtree[id][v].e2=s+1;
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(id,pos,s,e,l,mid,v*2);
else update(id,pos,s,e,mid+1,r,v*2+1);
segtree[id][v]=merge(segtree[id][v*2],segtree[id][v*2+1]);
}
node query(int id,int tl,int tr,int l=1,int r=n-1,int v=1){
if(r<tl or tr<l){
return trash;
}
if(tl<=l and r<=tr){
return segtree[id][v];
}
int mid=(l+r)/2;
return merge(query(id,tl,min(mid,tr),l,mid,v*2),query(id,max(mid+1,tl),tr,mid+1,r,v*2+1));
}
signed main() {_
trash.sz=-1;
cin>>n>>q;
for(int i=1;i<n;i++){
cin>>L[i]>>R[i];
}
build(0);
reverse(L+1,L+n);
reverse(R+1,R+n);
build(1);
reverse(L+1,L+n);
reverse(R+1,R+n);
for(int i=0;i<q;i++){
int t;
cin>>t;
if(t==1){
ll p,s,e;
cin>>p>>s>>e;
update(0,p,s,e);
update(1,n-p,s,e);
}
else{
ll a,b,c,d;
cin>>a>>b>>c>>d;
if(a==c){
cout<<max(0ll,b-d)<<'\n';
continue;
}
node tmp;
if(a<c){
tmp=query(0,a,c-1);
}
else{
a=n-a+1;
c=n-c+1;
//swap(b,d);
tmp=query(1,a,c-1);
}
/*cout<<tmp.sz<<'\n';
cout<<tmp.s1<<' '<<tmp.s2<<'\n';
cout<<tmp.e1<<' '<<tmp.e2<<'\n';
cout<<tmp.c1<<' '<<tmp.c2<<'\n';*/
ll ans=0;
int fin;
if(b>tmp.s1){
ans+=tmp.c1+(b-tmp.s1);
fin=tmp.e1;
}
else if(b>=tmp.s2){
ll dif=tmp.c1-tmp.c2;
ans+=tmp.c2+max(0ll,dif-(tmp.s1-b));
ll res=b+tmp.sz;
if(res>tmp.e1){
fin=tmp.e1;
}
else{
fin=max(res,tmp.e2);
}
}
else{
ans+=tmp.c2;
fin=tmp.e2;
}
cout<<ans+max(0ll,fin-d)<<'\n';;
}
}
return 0;
}
//maybe its multiset not set
Compilation message
timeleap.cpp: In function 'node merge(node, node)':
timeleap.cpp:47:36: error: no matching function for call to 'max(int&, long long int&)'
47 | ans.e1=max(res,b.e2);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from timeleap.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
timeleap.cpp:47:36: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
47 | ans.e1=max(res,b.e2);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from timeleap.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
timeleap.cpp:47:36: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
47 | ans.e1=max(res,b.e2);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from timeleap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
timeleap.cpp:47:36: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
47 | ans.e1=max(res,b.e2);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from timeleap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
timeleap.cpp:47:36: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
47 | ans.e1=max(res,b.e2);
| ^
timeleap.cpp:69:36: error: no matching function for call to 'max(int&, long long int&)'
69 | ans.e2=max(res,b.e2);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from timeleap.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
timeleap.cpp:69:36: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
69 | ans.e2=max(res,b.e2);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from timeleap.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
timeleap.cpp:69:36: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
69 | ans.e2=max(res,b.e2);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from timeleap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
timeleap.cpp:69:36: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
69 | ans.e2=max(res,b.e2);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from timeleap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
timeleap.cpp:69:36: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
69 | ans.e2=max(res,b.e2);
| ^
timeleap.cpp: In function 'void setIO(std::string)':
timeleap.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
