#include <bits/stdc++.h>
/*
"Tree segtree" (HLD)
Backwards?
Intervals overlap -> fine
Intervals do not overlap -> single point
*/
struct node{
long long delay,min,max,start,back;//max(min(x+delay,max),min) (max is when num. leaps start increasing)
node(long long a=0,long long b=-1e18,long long c=1e18,long long d=1e18,long long e=0){
delay=a,min=b,max=c,start=d,back=e;
}
node combine(node oth){
node undel=node(delay+oth.delay,min+oth.delay,max+oth.delay,start+oth.delay,back+oth.back);//put oth's delay at start
long long fmin=std::max(std::min(undel.min,oth.max),oth.min);//clamp to next one
long long fmax=std::max(std::min(undel.max,oth.max),oth.min);//clamp to next one
long long fstart=min==max?undel.start:std::min(std::max(oth.start,undel.min),undel.max);//clamp to this one if there is a range, otherwise just use this start
long long fback=std::min(1e18,back+oth.back+std::max(0ll,undel.min-oth.start));//cap for overflow
return node(delay+oth.delay,fmin,fmax,fstart,fback);
}
long long nleaps(long long st,long long et){
long long stdest=std::max(std::min(st+delay,max),min);
return std::max((st+delay)-start,0ll)+std::max(stdest-et,0ll)+back;
}
};
struct segtree{
int size;
std::vector<node> nodes,rnodes;//one forward, one reverse
segtree(int n){
size=n;
nodes.resize(2*n-1);
rnodes.resize(2*n-1);
}
void update(int p,node val,int nl,int nr,int ni){
if(p<nl||p>=nr)return;
if(nl+1>=nr){
nodes[ni]=val;
rnodes[ni]=val;
return;
}
int nm=(nl+nr)/2;
update(p,val,nl,nm,ni+1);
update(p,val,nm,nr,ni+2*(nm-nl));
nodes[ni]=nodes[ni+1].combine(nodes[ni+2*(nm-nl)]);
rnodes[ni]=rnodes[ni+2*(nm-nl)].combine(rnodes[ni+1]);
}
void update(int p,node val){update(p,val,0,size,0);}
node query(int l,int r,int nl,int nr,int ni){
if(l>=nr||r<=nl)return node();
if(l<=nl&&r>=nr)return nodes[ni];
int nm=(nl+nr)/2;
node res1=query(l,r,nl,nm,ni+1);
node res2=query(l,r,nm,nr,ni+2*(nm-nl));
return res1.combine(res2);
}
node query(int l,int r){return query(l,r,0,size,0);}
node rquery(int l,int r,int nl,int nr,int ni){
if(l>=nr||r<=nl)return node();
if(l<=nl&&r>=nr)return rnodes[ni];
int nm=(nl+nr)/2;
node res1=rquery(l,r,nl,nm,ni+1);
node res2=rquery(l,r,nm,nr,ni+2*(nm-nl));
return res2.combine(res1);
}
node rquery(int l,int r){return rquery(l,r,0,size,0);}
};
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n,q;
std::cin>>n>>q;
segtree seg(n);
for(int i=0;i<n-1;i++){
int a,b;
std::cin>>a>>b;
seg.update(i,node(1,a+1,b,b));
}
for(int i=0;i<q;i++){
int x;
std::cin>>x;
if(x==1){
int p,s,e;
std::cin>>p>>s>>e;
p--;
seg.update(p,node(1,s+1,e,e));
}else{
int a,b,c,d;
std::cin>>a>>b>>c>>d;
a--,c--;
if(a<c){
std::cout<<seg.query(a,c).nleaps(b,d)<<'\n';
}else{
std::cout<<seg.rquery(c,a).nleaps(b,d)<<'\n';
}
}
}
}
Compilation message
timeleap.cpp: In member function 'node node::combine(node)':
timeleap.cpp:20:86: error: no matching function for call to 'min(double, long long int)'
20 | long long fback=std::min(1e18,back+oth.back+std::max(0ll,undel.min-oth.start));//cap for overflow
| ^
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:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
timeleap.cpp:20:86: note: deduced conflicting types for parameter 'const _Tp' ('double' and 'long long int')
20 | long long fback=std::min(1e18,back+oth.back+std::max(0ll,undel.min-oth.start));//cap for overflow
| ^
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:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
timeleap.cpp:20:86: note: deduced conflicting types for parameter 'const _Tp' ('double' and 'long long int')
20 | long long fback=std::min(1e18,back+oth.back+std::max(0ll,undel.min-oth.start));//cap for overflow
| ^
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:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
timeleap.cpp:20:86: note: mismatched types 'std::initializer_list<_Tp>' and 'double'
20 | long long fback=std::min(1e18,back+oth.back+std::max(0ll,undel.min-oth.start));//cap for overflow
| ^
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:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
timeleap.cpp:20:86: note: mismatched types 'std::initializer_list<_Tp>' and 'double'
20 | long long fback=std::min(1e18,back+oth.back+std::max(0ll,undel.min-oth.start));//cap for overflow
| ^
