#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
struct item {
ll t=0, a=0, b=0, c=0;
};
const ll INF=1e18+7;
const int LIM=3e5+7;
item tr[2][4*LIM];
int N=1;
item merge(item a, item b) {
item x;
x.c=a.c+b.c;
if(a.t==0 && b.t==0) {
x.a=max(a.a, b.a);
x.b=min(a.b, b.b);
if(x.a<=x.b) return x;
if(a.a>b.b) {
x.a=a.a;
x.b=b.b;
x.c+=a.a-b.b;
} else {
x.a=a.b;
x.b=b.a;
}
x.t=1;
return x;
}
x.t=1;
if(b.t==0) {
x.a=a.a;
if(a.b>=b.b) {
x.b=b.b;
x.c+=a.b-b.b;
} else if(a.b<=b.a) x.b=b.a;
else x.b=a.b;
return x;
}
x.b=b.b;
if(a.t==0) {
if(a.a>=b.a) {
x.c+=a.a-b.a;
x.a=a.a;
} else if(a.b<=b.a) x.a=a.b;
else x.a=b.a;
} else {
x.a=a.a;
if(a.b>=b.a) x.c+=a.b-b.a;
}
return x;
}
void upd(int v, int k, item p) {
v+=N;
tr[k][v]=p;
v/=2;
while(v) {
tr[k][v]=merge(tr[k][2*v], tr[k][2*v+1]);
v/=2;
}
}
item cnt(int l, int r, int k) {
if(l>r) return {0, -INF, INF, 0};
l+=N; r+=N;
item ansl=tr[k][l];
if(l==r) return ansl;
item ansr=tr[k][r];
while(l/2!=r/2) {
if(l%2==0) ansl=merge(ansl, tr[k][l+1]);
if(r%2==1) ansr=merge(tr[k][r-1], ansr);
l/=2; r/=2;
}
return merge(ansl, ansr);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, q;
cin >> n >> q;
while(N<n) N*=2;
rep(i, n-1) {
ll a, b;
cin >> a >> b; --b;
tr[0][N+i]={0, a-i, b-i, 0};
tr[1][N+n-i-2]={0, a-(n-i-2), b-(n-i-2), 0};
}
for(int i=N-1; i; --i) {
tr[0][i]=merge(tr[0][2*i], tr[0][2*i+1]);
tr[1][i]=merge(tr[1][2*i], tr[1][2*i+1]);
}
while(q--) {
int t;
cin >> t;
if(t==2) {
ll a, b, c, d;
cin >> a >> b >> c >> d; --a; --c;
if(a<=c) {
b-=a; d-=c;
item x={1, b, b, 0}, y={1, d, d};
x=merge(x, cnt(a, c-1, 0));
x=merge(x, y);
cout << x.c << '\n';
continue;
}
b-=(n-a-2); d-=(n-c-2);
item x={1, b, b, 0}, y={1, d, d};
x=merge(x, cnt(n-a-1, n-c-2, 1));
x=merge(x, y);
cout << x.c << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
287 ms |
73576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
