//#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{
int s1,s2,e1,e2,sz;
ll c1,c2;
};
const int mxn=3e5+5;
vector<vector<node>> segtree(2,vector<node>(mxn*4));
int n,q;
int L[mxn],R[mxn];
node trash;
int cnt=0;
void merge(node &ans,node &a,node &b){
if(a.sz==-1){
ans=b;
return;
}
if(b.sz==-1){
ans=a;
return;
}
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){
ll 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){
ll 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;
}
}
}
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);
if(segtree[id][v*2].sz==-1){
segtree[id][v]=segtree[id][v*2+1];
return;
}
if(segtree[id][v*2+1].sz==-1){
segtree[id][v]=segtree[id][v*2];
return;
}
segtree[id][v].sz=segtree[id][v*2].sz+segtree[id][v*2+1].sz;
segtree[id][v].s1=segtree[id][v*2].s1;
segtree[id][v].s2=segtree[id][v*2].s2;
{
segtree[id][v].c1=segtree[id][v*2].c1;
if(segtree[id][v*2].e1>segtree[id][v*2+1].s1){
segtree[id][v].c1+=segtree[id][v*2+1].c1+(segtree[id][v*2].e1-segtree[id][v*2+1].s1);
segtree[id][v].e1=segtree[id][v*2+1].e1;
}
else if(segtree[id][v*2].e1>=segtree[id][v*2+1].s2){
ll dif=segtree[id][v*2+1].c1-segtree[id][v*2+1].c2;
segtree[id][v].c1+=segtree[id][v*2+1].c2+max(0ll,dif-(segtree[id][v*2+1].s1-segtree[id][v*2].e1));
int res=segtree[id][v*2].e1+segtree[id][v*2+1].sz;
if(res>segtree[id][v*2+1].e1){
segtree[id][v].e1=segtree[id][v*2+1].e1;
}
else{
segtree[id][v].e1=max(res,segtree[id][v*2+1].e2);
}
}
else{
segtree[id][v].c1+=segtree[id][v*2+1].c2;
segtree[id][v].e1=segtree[id][v*2+1].e2;
}
}
{
segtree[id][v].c2=segtree[id][v*2].c2;
if(segtree[id][v*2].e2>segtree[id][v*2+1].s1){
segtree[id][v].c2+=segtree[id][v*2+1].c1+(segtree[id][v*2].e2-segtree[id][v*2+1].s1);
segtree[id][v].e2=segtree[id][v*2+1].e1;
}
else if(segtree[id][v*2].e2>=segtree[id][v*2+1].s2){
ll dif=segtree[id][v*2+1].c1-segtree[id][v*2+1].c2;
segtree[id][v].c2+=segtree[id][v*2+1].c2+max(0ll,dif-(segtree[id][v*2+1].s1-segtree[id][v*2].e2));
int res=segtree[id][v*2].e2+segtree[id][v*2+1].sz;
if(res>segtree[id][v*2+1].e1){
segtree[id][v].e2=segtree[id][v*2+1].e1;
}
else{
segtree[id][v].e2=max(res,segtree[id][v*2+1].e2);
}
}
else{
segtree[id][v].c2+=segtree[id][v*2+1].c2;
segtree[id][v].e2=segtree[id][v*2+1].e2;
}
}
}
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);
if(segtree[id][v*2].sz==-1){
segtree[id][v]=segtree[id][v*2+1];
return;
}
if(segtree[id][v*2+1].sz==-1){
segtree[id][v]=segtree[id][v*2];
return;
}
segtree[id][v].sz=segtree[id][v*2].sz+segtree[id][v*2+1].sz;
segtree[id][v].s1=segtree[id][v*2].s1;
segtree[id][v].s2=segtree[id][v*2].s2;
{
segtree[id][v].c1=segtree[id][v*2].c1;
if(segtree[id][v*2].e1>segtree[id][v*2+1].s1){
segtree[id][v].c1+=segtree[id][v*2+1].c1+(segtree[id][v*2].e1-segtree[id][v*2+1].s1);
segtree[id][v].e1=segtree[id][v*2+1].e1;
}
else if(segtree[id][v*2].e1>=segtree[id][v*2+1].s2){
ll dif=segtree[id][v*2+1].c1-segtree[id][v*2+1].c2;
segtree[id][v].c1+=segtree[id][v*2+1].c2+max(0ll,dif-(segtree[id][v*2+1].s1-segtree[id][v*2].e1));
int res=segtree[id][v*2].e1+segtree[id][v*2+1].sz;
if(res>segtree[id][v*2+1].e1){
segtree[id][v].e1=segtree[id][v*2+1].e1;
}
else{
segtree[id][v].e1=max(res,segtree[id][v*2+1].e2);
}
}
else{
segtree[id][v].c1+=segtree[id][v*2+1].c2;
segtree[id][v].e1=segtree[id][v*2+1].e2;
}
}
{
segtree[id][v].c2=segtree[id][v*2].c2;
if(segtree[id][v*2].e2>segtree[id][v*2+1].s1){
segtree[id][v].c2+=segtree[id][v*2+1].c1+(segtree[id][v*2].e2-segtree[id][v*2+1].s1);
segtree[id][v].e2=segtree[id][v*2+1].e1;
}
else if(segtree[id][v*2].e2>=segtree[id][v*2+1].s2){
ll dif=segtree[id][v*2+1].c1-segtree[id][v*2+1].c2;
segtree[id][v].c2+=segtree[id][v*2+1].c2+max(0ll,dif-(segtree[id][v*2+1].s1-segtree[id][v*2].e2));
int res=segtree[id][v*2].e2+segtree[id][v*2+1].sz;
if(res>segtree[id][v*2+1].e1){
segtree[id][v].e2=segtree[id][v*2+1].e1;
}
else{
segtree[id][v].e2=max(res,segtree[id][v*2+1].e2);
}
}
else{
segtree[id][v].c2+=segtree[id][v*2+1].c2;
segtree[id][v].e2=segtree[id][v*2+1].e2;
}
}
}
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;
if(!(mid<tl or min(mid,tr)<l)) return query(id,max(mid+1,tl),tr,mid+1,r,v*2+1);
if(!(r<min(tl,mid+1) or tr<mid+1)) return query(id,tl,min(mid,tr),l,mid,v*2);
node a=query(id,tl,min(mid,tr),l,mid,v*2);
node b=query(id,max(mid+1,tl),tr,mid+1,r,v*2+1);
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){
ll 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){
ll 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;
}
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{
int a,b,c,d;
cin>>a>>b>>c>>d;
if(a==c){
cout<<max(0,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));
int 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(0,fin-d)<<'\n';;
}
}
return 0;
}
//maybe its multiset not set
Compilation message
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
141144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
194 ms |
141148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
141144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
