#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int32_t,int32_t>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod=1e9+7,mxn=3e5,inf=1e9,minf=-1e9,lg=20,Mxn=1e6;
//#undef int
int n,k,m,d,q;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int L[mxn+10],R[mxn+10];
int L2[mxn+10],R2[mxn+10];
pair<pii,int> go[mxn+10][lg+1][2];
pair<pii,int> go2[mxn+10][lg+1][2];
struct seg{
int32_t mn[4*mxn+10];
void init(){for(int i=0;i<=4*n;i++)mn[i]=inf;}
void pull(int pos){mn[pos]=min(mn[pos<<1],mn[pos<<1|1]);}
void update(int qpos,int x,int pos=1,int l=1,int r=n){
if(l>qpos||r<qpos)return;
if(l==r)return void(mn[pos]=x);
int mid=(l+r)>>1;
update(qpos,x,pos<<1,l,mid);
update(qpos,x,pos<<1|1,mid+1,r);
pull(pos);
}
int get_first(int ql,int qr,int x,int pos=1,int l=1,int r=n){
//find first x>mn[pos]
if(l>qr||r<ql)return n;
if(mn[pos]>=x)return n;
int mid=(l+r)>>1;
if(ql<=l&&r<=qr){
if(l==r){
if(mn[pos]<x)return l;
return n;
}
}
int y=get_first(ql,qr,x,pos<<1,l,mid);
if(y!=n)return y;
return get_first(ql,qr,x,pos<<1|1,mid+1,r);
}
}t,T;
struct seg2{
int32_t mx[4*mxn+10];
void init(){for(int i=0;i<=4*n;i++)mx[i]=minf;}
void pull(int pos){mx[pos]=max(mx[pos<<1],mx[pos<<1|1]);}
void update(int qpos,int x,int pos=1,int l=1,int r=n){
if(l>qpos||r<qpos)return;
if(l==r)return void(mx[pos]=x);
int mid=(l+r)>>1;
update(qpos,x,pos<<1,l,mid);
update(qpos,x,pos<<1|1,mid+1,r);
pull(pos);
}
int get_first(int ql,int qr,int x,int pos=1,int l=1,int r=n){
//find first x<mx[pos]
if(l>qr||r<ql)return n;
if(mx[pos]<=x)return n;
int mid=(l+r)>>1;
if(ql<=l&&r<=qr){
if(l==r){
if(mx[pos]>x)return l;
return n;
}
}
int y=get_first(ql,qr,x,pos<<1,l,mid);
if(y!=n)return y;
return get_first(ql,qr,x,pos<<1|1,mid+1,r);
}
}t2,T2;
void cal(){
t.init();
t2.init();
for(int i=1;i<=n-1;i++){
t.update(i,R[i]-i);
t2.update(i,L[i]-i);
}
for(int i=0;i<=lg;i++)for(int j=0;j<2;j++)go[n][i][j]={{n,j},0};
for(int i=1;i<=n-1;i++){
int a,b;
a=t.get_first(i,n,R[i]-i);
b=t2.get_first(i,n,R[i]-i);
if(a<b)go[i][0][1]={{a,1},R[i]+a-i-R[a]};
else go[i][0][1]={{b,0},0};
a=t.get_first(i,n,L[i]-i);
b=t2.get_first(i,n,L[i]-i);
if(a<b)go[i][0][0]={{a,1},L[i]+a-i-R[a]};
else go[i][0][0]={{b,0},0};
}
for(int j=1;j<=lg;j++){
for(int i=1;i<=n-1;i++){
for(int k=0;k<2;k++){
pair<pii,int>x=go[go[i][j-1][k].f.f][j-1][go[i][j-1][k].f.s];
go[i][j][k].f=x.f;
go[i][j][k].s=go[i][j-1][k].s+x.s;
}
}
}
}
void cal2(){
T.init();
T2.init();
for(int i=1;i<=n-1;i++){
T.update(i,R2[i]-i);
T2.update(i,L2[i]-i);
}
for(int i=0;i<=lg;i++)for(int j=0;j<2;j++)go2[n][i][j]={{n,j},0};
for(int i=1;i<=n-1;i++){
int a,b;
a=T.get_first(i,n,R2[i]-i);
b=T2.get_first(i,n,R2[i]-i);
if(a<b)go2[i][0][1]={{a,1},R2[i]+a-i-R2[a]};
else go2[i][0][1]={{b,0},0};
a=T.get_first(i,n,L2[i]-i);
b=T2.get_first(i,n,L2[i]-i);
if(a<b)go2[i][0][0]={{a,1},L2[i]+a-i-R2[a]};
else go2[i][0][0]={{b,0},0};
}
for(int j=1;j<=lg;j++){
for(int i=1;i<=n-1;i++){
for(int k=0;k<2;k++){
pair<pii,int>x=go2[go2[i][j-1][k].f.f][j-1][go2[i][j-1][k].f.s];
go2[i][j][k].f=x.f;
go2[i][j][k].s=go2[i][j-1][k].s+x.s;
}
}
}
}
int32_t main(){
fastio
cin>>n>>q;
for(int i=1;i<=n-1;i++){
cin>>L[i]>>R[i],R[i]--;
L2[n-i]=L[i];
R2[n-i]=R[i];
}
cal();
cal2();
while(q--){
int ty;cin>>ty;
if(ty==2){
int a,b,c,d;cin>>a>>b>>c>>d;
if(a<=c){
int x=t.get_first(a,n,b-a);
int y=t2.get_first(a,n,b-a);
if(min(x,y)>=c)cout<<max(0LL,b+c-a-d)<<'\n';
else{
ll ans=0;
pii cur;
if(x<y)cur={x,1},ans+=(b+x-a-R[x]);
else cur={y,0};
for(int i=lg;i>=0;i--){
if(go[cur.f][i][cur.s].f.f<c){
ans+=(1LL)*go[cur.f][i][cur.s].s;
cur=go[cur.f][i][cur.s].f;
}
}
int g;
if(cur.s==0)g=L[cur.f];
else g=R[cur.f];
g+=c-cur.f;
ans+=(1LL)*max(0LL,g-d);
cout<<ans<<'\n';
}
}
else{
a=n-a+1;
c=n-c+1;
int x=T.get_first(a,n,b-a);
int y=T2.get_first(a,n,b-a);
if(min(x,y)>=c)cout<<max(0LL,b+c-a-d)<<'\n';
else{
ll ans=0;
pii cur;
if(x<y)cur={x,1},ans+=(b+x-a-R2[x]);
else cur={y,0};
for(int i=lg;i>=0;i--){
if(go2[cur.f][i][cur.s].f.f<c){
ans+=(1LL)*go2[cur.f][i][cur.s].s;
cur=go2[cur.f][i][cur.s].f;
}
}
int g;
if(cur.s==0)g=L2[cur.f];
else g=R2[cur.f];
g+=c-cur.f;
ans+=(1LL)*max(0LL,g-d);
cout<<ans<<'\n';
}
}
}
else{
int a,b,c;cin>>a>>b>>c;
L[a]=b;
R[a]=c-1;
L2[n-a]=L[a];
R2[n-a]=R[a];
cal();
cal2();
}
}
}
/*
*/
Compilation message (stderr)
timeleap.cpp:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
16 | #pragma GCC optimize ("03,unroll-lopps")
| ^
timeleap.cpp:23:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
23 | void setIO(string name){
| ^
timeleap.cpp:36:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
36 | void init(){for(int i=0;i<=4*n;i++)mn[i]=inf;}
| ^
timeleap.cpp:37:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
37 | void pull(int pos){mn[pos]=min(mn[pos<<1],mn[pos<<1|1]);}
| ^
timeleap.cpp:38:61: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
38 | void update(int qpos,int x,int pos=1,int l=1,int r=n){
| ^
timeleap.cpp:46:68: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
46 | int get_first(int ql,int qr,int x,int pos=1,int l=1,int r=n){
| ^
timeleap.cpp:65:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
65 | void init(){for(int i=0;i<=4*n;i++)mx[i]=minf;}
| ^
timeleap.cpp:66:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
66 | void pull(int pos){mx[pos]=max(mx[pos<<1],mx[pos<<1|1]);}
| ^
timeleap.cpp:67:61: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
67 | void update(int qpos,int x,int pos=1,int l=1,int r=n){
| ^
timeleap.cpp:75:68: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
75 | int get_first(int ql,int qr,int x,int pos=1,int l=1,int r=n){
| ^
timeleap.cpp:92:10: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
92 | void cal(){
| ^
timeleap.cpp:124:11: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
124 | void cal2(){
| ^
timeleap.cpp:155:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
155 | int32_t main(){
| ^
timeleap.cpp: In function 'void setIO(std::string)':
timeleap.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
