// ~Be name khoda~ //
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
const int maxn = 1e6 + 10;
const int maxn5 = 3e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 2e18;
struct javab{
ll ans, st, ft, ub, ch;
bool rad;
javab(){
rad = true;
}
} node1[maxnt], node2[maxnt];
javab operator +(javab a, javab b){
if(a.rad)
return b;
if(b.rad)
return a;
//cout << "operator having " << '\n';
//cout << a.st << ' ' << a.ft << ' ' << a.ub << ' ' << a.ch << '\n';
//cout << b.st << ' ' << b.ft << ' ' << b.ub << ' ' << b.ch << '\n';
javab ret;
ret.rad = false;
ret.st = a.st;
ret.ans = a.ans + b.ans;
if(a.ft <= b.st){
ret.ft = b.ft;
if(a.ch <= a.ub){
ll ft = a.ft + (a.ub - a.ch + 1);
if(ft < b.st){
ret.ub = a.ub;
ret.ch = ret.ub + 2;
if(ret.ch == ret.st)
ret.ch++;
return ret;
}
ret.ub = a.ub;
if(ft > b.ub)
ret.ub -= ft - b.ub;
ft = a.ft + (a.ch <= ret.ub ? ret.ub - a.ch + 1 : 0);
if(ft >= b.ch)
ret.ch = ret.ub - (ft - b.ch);
else
ret.ch = ret.ub + 2;
if(ret.ch == ret.st)
ret.ch++;
return ret;
}
ret.ub = a.ub;
ret.ch = a.ch;
if(ret.ch == ret.st)
ret.ch++;
return ret;
}
if(a.ft > b.ub){
ret.ans += a.ft - b.ub;
ret.ft = b.ft + (b.ch <= b.ub ? b.ub - b.ch + 1 : 0);
ret.ub = a.ch - 1;
ret.ch = ret.ub + 2;
return ret;
}
ret.ft = b.ft + (a.ft >= b.ch ? a.ft - b.ch + 1 : 0);
ll ft = a.ft + (a.ub >= a.ch ? a.ub - a.ch + 1 : 0);
if(ft > b.ub){
a.ub -= ft - b.ub;
ft = b.ub;
}
//cout << a.ub << '\n';
ret.ub = min(a.ub, a.ch + b.ub - a.ft - 1);
if(ret.ub < a.ch){
ret.ch = ret.ub + 2;
}
else{
ret.ch = a.ch;
if(b.ch > a.ft + 1){
if(b.ch > ft){
ret.ch = ret.ub + 2;
}
else{
ret.ch += b.ch - (a.ft + 1);
}
}
}
if(ret.ch == a.st)
ret.ch++;
return ret;
}
ll ls[maxn5], rs[maxn5];
inline javab recal(javab a, ll ti){
javab b;
b.rad = false;
b.st = ti;
b.ft = ti;
b.ub = ti;
b.ch = ti + 2;
b.ans = 0;
return b + a;
}
inline void build(int l, int r, int v){
if(r - l == 1){
node1[v].ans = node2[v].ans = 0;
node1[v].st = node2[v].st = ls[l];
node1[v].ft = node2[v].ft = ls[l] + 1;
node1[v].ub = node2[v].ub = rs[l] - 1;
node1[v].ch = node2[v].ch = ls[l] + 1;
node1[v].rad = node2[v].rad = false;
return;
}
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
node1[v] = node1[v * 2] + node1[v * 2 + 1];
node2[v] = node2[v * 2 + 1] + node2[v * 2];
return;
}
inline void upd(int l, int r, int ind, int v){
if(r - l == 1){
node1[v].ans = node2[v].ans = 0;
node1[v].st = node2[v].st = ls[l];
node1[v].ft = node2[v].ft = ls[l] + 1;
node1[v].ub = node2[v].ub = rs[l] - 1;
node1[v].ch = node2[v].ch = ls[l] + 1;
node1[v].rad = node2[v].rad = false;
return;
}
int mid = (l + r) >> 1;
if(ind < mid)
upd(l, mid, ind, v * 2);
else
upd(mid, r, ind, v * 2 + 1);
node1[v] = node1[v * 2] + node1[v * 2 + 1];
node2[v] = node2[v * 2 + 1] + node2[v * 2];
return;
}
inline javab get1(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq){
javab a;
return a;
}
if(lq <= l && r <= rq){
//cout << "perfect result of " << l << ' ' << r << '\n';
//cout << node1[v].st << ' ' << node1[v].ft << ' ' << node1[v].ub << ' ' << node1[v].ch << '\n';
return node1[v];
}
//cout << "very well " << l << ' ' << r << '\n';
int mid = (l + r) >> 1;
return get1(l, mid, lq, rq, v * 2) + get1(mid, r, lq, rq, v * 2 + 1);
}
inline javab get2(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq){
javab a;
return a;
}
if(lq <= l && r <= rq){
//cout << "perfect result of " << l << ' ' << r << '\n';
//cout << node2[v].st << ' ' << node2[v].ft << ' ' << node2[v].ub << ' ' << node2[v].ch << '\n';
return node2[v];
}
//cout << "very well " << l << ' ' << r << '\n';
int mid = (l + r) >> 1;
return get2(mid, r, lq, rq, v * 2 + 1) + get2(l, mid, lq, rq, v * 2);
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n, q; cin >> n >> q;
n--;
for(int i = 0; i < n; i++)
cin >> ls[i] >> rs[i];
build(0, n, 1);
for(int i = 0; i < q; i++){
int ty; cin >> ty;
if(ty == 1){
int p, s, e; cin >> p >> s >> e;
p--;
ls[p] = s;
rs[p] = e;
upd(0, n, p, 1);
}
else{
ll a, b, c, d; cin >> a >> b >> c >> d;
a--; c--;
if(a == c){
cout << (b > d ? b - d : 0) << '\n';
continue;
}
javab re;
if(a < c){
re = get1(0, n, a, c, 1);
}
else{
re = get2(0, n, c, a, 1);
}
//cout << re.st << ' ' << re.ft << ' ' << re.ans << ' ' << re.ub << ' ' << re.ch << '\n';
re = recal(re, b);
if(re.ft > d)
re.ans += re.ft - d;
cout << re.ans << '\n';
}
}
}
/*
5 1
3 5
4 8
2 6
5 10
2 5 3 1 10
3 1
0 5
0 5
2 1 3 3 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
112964 KB |
Output is correct |
| 2 |
Incorrect |
40 ms |
112968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
613 ms |
137132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
112964 KB |
Output is correct |
| 2 |
Incorrect |
40 ms |
112968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
