#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;typedef long double ld;typedef unsigned long long ul;typedef unsigned int ui;typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cerr << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cerr << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cerr << endl;}
int n,q,in[300010][2];
struct Node{
ll b,x,ls,le,rs,re,si=0;
Node(){};
Node(ll bb,int xx,int i,int j,int k,int l){b=bb;x=xx;ls=i;le=j;rs=k;re=l;}
Node operator +(Node B){
B.x--;B.ls--;B.le--;
Node p = Node(b,x,ls,le,rs,re);
if(p.re>B.x) p.x-=(p.re-B.x);
if(p.x<p.ls){
p.b+=(p.ls-p.x);
p.x=p.ls;
}
p.b+=B.b;
ll t = B.re-B.rs, ss = B.rs-B.si-1;
p.rs = max(p.rs,B.ls);
p.re = max(p.re,B.ls);
if(p.rs<=ss) p.rs = B.rs;
else p.rs = B.rs + min(p.rs-ss,t);
if(p.re<=ss) p.re = B.rs;
else p.re = B.rs + min(p.re-ss,t);
p.si = si + B.si + 1;
return p;
}
void pr(){
prl("b=",b,"x=",x,"[",ls,",",le,"]"," [",rs,",",re,"]");
}
};
vector<Node> help;
struct SEG{
Node val[1200000];
void init(int x, int l, int r, bool t){
if(l==r){
if(t)val[x]=Node(0,in[l][1],in[l][0],in[l][1],in[l][0],in[l][1]);
else val[x]=Node(0,in[n-l][1],in[n-l][0],in[n-l][1],in[n-l][0],in[n-l][1]);
return ;
}
init(x*2,l,(l+r)/2,t);
init(x*2+1,(l+r)/2+1,r,t);
val[x]=val[x*2]+val[x*2+1];
}
void gang(int x, int l, int r, int ind, bool t){
if(r<ind||ind<l) return ;
if(l==r){
if(t)val[x]=Node(0,in[l][1],in[l][0],in[l][1],in[l][0],in[l][1]);
else val[x]=Node(0,in[n-l][1],in[n-l][0],in[n-l][1],in[n-l][0],in[n-l][1]);
return ;
}
gang(x*2,l,(l+r)/2,ind,t);
gang(x*2+1,(l+r)/2+1,r,ind,t);
val[x]=val[x*2]+val[x*2+1];
}
void query(int x, int l, int r,int s, int e){
if(r<s||e<l) return ;
if(s<=l&&r<=e){
help.eb(val[x]);return ;
}
query(x*2,l,(l+r)/2,s,e);
query(x*2+1,(l+r)/2+1,r,s,e);
}
void debug(int x, int l, int r){
prl("#######x=",x,"l=",l,"r=",r);
val[x].pr();
if(l==r)return ;
debug(x*2,l,(l+r)/2);debug(x*2+1,(l+r)/2+1,r);
}
}seg1, seg2;
ll eval(ll s, ll e){
for(int i=0;i<help.size()-1;i++) help[i]=help[i]+help[i+1];
s = max(help[0].ls,s);
ll ret = help[0].b + max(s-help[0].x,0LL);
ll ss = help[0].rs-help[0].si;
ll t = help[0].rs+1;
if(s>ss) t = help[0].rs + min(help[0].re-help[0].rs,s-ss)+1;
ret+=max(t-e,0LL);
return ret;
}
int main(){
fastio;
cin>>n>>q;
for(int i=1;i<n;i++){
cin>>in[i][0]>>in[i][1];
in[i][1]--;
}
seg1.init(1,1,n-1,1);
seg2.init(1,1,n-1,0);
//prl("seg1");seg1.debug(1,1,n-1);
//prl("seg2");seg2.debug(1,1,n-1);
while(q--){
int a,b,c,d;
cin>>a;
if(a==1){
cin>>a>>b>>c;
in[a][0]=b;in[a][1]=c-1;
seg1.gang(1,1,n-1,a,1);
seg2.gang(1,1,n-1,n-a,0);
/*
prl("after query=================");
prl("seg1");seg1.debug(1,1,n-1);
prl("seg2");seg2.debug(1,1,n-1);
*/
}
else{
cin>>a>>b>>c>>d;
help.clear();
ll ans=0;
if(a<c){
seg1.query(1,1,n-1,a,c-1);
ans = eval(b,d);
}
else if(a>c){
a = n-a;c = n-c;
seg2.query(1,1,n-1,a+1,c);
ans = eval(b,d);
}
else ans = max(b-d,0);
cout<<ans<<"\n";
}
}
}
Compilation message
timeleap.cpp: In function 'll eval(ll, ll)':
timeleap.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<help.size()-1;i++) help[i]=help[i]+help[i+1];
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
131832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
723 ms |
136948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
131832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
