#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
const long long inf = -1e18;
struct Node{
long long val[2][2];
Node(){
for (int i = 0; i < 2; ++ i)
for (int j = 0; j < 2; ++ j) val[i][j] = inf;
val[0][0] = 0;
}
};
Node mer(Node a, Node b){
Node c;
for (int i = 0; i < 2; ++ i){
for (int j = 0; j < 2; ++ j) c.val[i][j] = max(a.val[i][j], b.val[i][j]);
}
for (int i = 0; i < 2; ++ i){
for (int l = 0; l < 2; ++ l){
for (int j = 0; j < 2; ++ j) c.val[i][j] = max(c.val[i][j], a.val[i][l] + b.val[l][j]);
}
}
return c;
}
struct Segtree{
Node it[4 * N];
void update(int s, int l, int r, int u, int i, int j){
//if (i == j && i == 3 && u == 3) cout << l << ' ' << r << ' ' << u << endl;
if (l == r){
it[s].val[0][0] = 0;
it[s].val[1][0] = l - j;
it[s].val[0][1] = i - l;
return;
}
int mid = l + r >> 1;
if (mid >= u) update(2 * s, l, mid, u, i, j);
else update(2 * s + 1, mid + 1, r, u, i, j);
it[s] = mer(it[2 * s], it[2 * s + 1]);
}
Node get(int s, int l, int r, int u, int v){
if (u <= l && r <= v) return it[s];
int mid = l + r >> 1;
Node a, b;
int bl = 0, br = 0;
if (mid >= u) a = get(2 * s, l, mid, u, v), bl = 1;
if (mid + 1 <= v) b = get(2 * s + 1, mid + 1, r, u, v), br = 1;
if (!bl) return b;
if (!br) return a;
return mer(a, b);
}
} seg1, seg2;
int in[N], out[N], n, q;
void solve(){
cin >> n >> q;
for (int i = 1; i <= n - 1; ++ i){
cin >> in[i] >> out[i];
seg1.update(1, 0, n, i, in[i], out[i] - 1);
seg2.update(1, 0, n, n - i, in[i], out[i] - 1);
}
while (q --){
int t; cin >> t;
if (t & 1){
int i; cin >> i;
cin >> in[i] >> out[i];
seg1.update(1, 0, n, i, in[i], out[i] - 1);
seg2.update(1, 0, n, n - i, in[i], out[i] - 1);
}
else {
int s, ts, e, te;
cin >> s >> ts >> e >> te;
if (s <= e){
seg1.update(1, 0, n, s - 1, ts - 1, ts - 1);
seg1.update(1, 0, n, e, te, te);
//cout << t << ' ' << s << ' ' << ts << ' ' << e << ' ' << te endl;
//cout << it[7].val[1][0] << endl;
cout << seg1.get(1, 0, n, s - 1, e).val[0][0] << '\n';
seg1.update(1, 0, n, s - 1, in[s - 1], out[s - 1] - 1);
seg1.update(1, 0, n, e, in[e], out[e] - 1);
}
else {
swap(s, e);
seg2.update(1, 0, n, n - e, ts - 1, ts - 1);
seg2.update(1, 0, n, n - s + 1, te, te);
//cout << n - e << ' ' << ts - 1 << ' ' << ts - 1 << endl;
//for (int i = n - e + 1; i < n - s + 1; ++ i) cout << i << ' ' << in[n - i] << ' ' << out[n - i] - 1 << endl;
//cout << n - s + 1 << ' ' << te << ' ' << te << endl;
cout << seg2.get(1, 0, n, n - e - 1, n + 1 - s).val[0][0] << '\n';
seg2.update(1, 0, n, n - e, in[e], out[e] - 1);
seg2.update(1, 0, n, n + 1 - s, in[s - 1], out[s - 1] - 1);
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Compilation message
timeleap.cpp: In member function 'void Segtree::update(long long int, long long int, long long int, long long int, long long int, long long int)':
timeleap.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid = l + r >> 1;
| ~~^~~
timeleap.cpp: In member function 'Node Segtree::get(long long int, long long int, long long int, long long int, long long int)':
timeleap.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
75612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1084 ms |
96064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
75612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
