#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
const int inf = 1e9;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );
int n;
struct Node {
int be, en, cur, usage;
bool flag;
Node(int _be = 0, int _en = 0, int _cur = -inf, int _usage = 0, bool _flag = false)
: be(_be), en(_en), cur(_cur), usage(_usage), flag(_flag) {}
Node operator + (const Node &_) const {
Node ret(0, 0, -inf, usage + _.usage);
if (cur == -inf && _.cur == -inf) {
ret.be = max(be, _.be);
ret.en = min(en, _.en);
if (ret.be >= ret.en) {
ret.be = be; ret.en = en;
if (en <= _.be) ret.cur = _.be;
else ret.cur = _.en - 1, ret.usage += be - _.en + 1, ret.flag = true;
}
}
else if (cur == -inf) {
ret.be = max(be, _.be);
ret.en = min(en, _.en);
if (ret.be < ret.en) {
ret.usage += (_.flag ? ret.be - _.be : 0);
ret.flag = _.flag;
}
else {
ret.be = be; ret.en = en;
if (be >= _.en) ret.usage += be - _.en + 1, ret.flag = true;
}
ret.cur = _.cur;
}
else if (_.cur == -inf) {
ret.be = be; ret.en = en;
if (_.be <= cur && cur < _.en) ret.cur = cur;
else if (cur < _.be) ret.cur = _.be;
else ret.cur = _.en - 1, ret.usage += cur - _.en + 1;
ret.flag = flag;
}
else {
ret.be = be; ret.en = en;
ret.cur = _.cur;
if (_.be <= cur && cur < _.en) ret.usage += _.flag ? cur - _.be : 0;
else if (cur < _.be) {}
else ret.usage += cur - _.en + 1 + (_.flag ? _.en - 1 - _.be : 0);
ret.flag = flag;
}
return ret;
}
};
struct It {
#define lC (i << 1)
#define rC (i << 1 | 1)
#define Mid ( (Left + Right) >> 1)
#define rt int i = 1, int Left = 0, int Right = n - 2
vector<Node> node;
It(int nNode) { node.assign(nNode, Node() ); }
void upd(int pos, Node val, rt) {
if (Left == Right) {
node[i] = val;
return ;
}
if (pos <= Mid) upd(pos, val, lC, Left, Mid);
else upd(pos, val, rC, Mid + 1, Right);
node[i] = node[lC] + node[rC];
}
Node get(int l, int r, rt) {
if (l <= Left && Right <= r) return node[i];
if (Mid < l) return get(l, r, rC, Mid + 1, Right);
else if (r <= Mid) return get(l, r, lC, Left, Mid);
else return get(l, r, lC, Left, Mid) + get(l, r, rC, Mid + 1, Right);
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef FourLeafClover
freopen("input", "r", stdin);
#endif // FourLeafCLover
cin >> n;
int q; cin >> q;
It it1( (n + 5) << 2),
it2( (n + 5) << 2);
for (int i = 0; i < n - 1; ++i) {
int l, r; cin >> l >> r;
it1.upd(i, Node(l - i, r - i) );
it2.upd(n - 2 - i, Node(l - (n - 2 - i), r - (n - 2 - i) ) );
}
while (q--) {
int type; cin >> type;
if (type == 1) {
int i, l, r; cin >> i >> l >> r; --i;
it1.upd(i, Node(l - i, r - i) );
it2.upd(n - 2 - i, Node(l - (n - 2 - i), r - (n - 2 - i) ) );
}
else {
int a, b, c, d; cin >> a >> b >> c >> d; --a; --c;
if (a == c) cout << max(0, b - d) << '\n';
else {
Node tmp;
if (a < c) tmp = it1.get(a, c - 1);
else tmp = it2.get(n - 1 - a, n - 1 - c - 1);
// cerr << tmp.be << ' ' << tmp.en << ' ' << tmp.cur << ' ' << tmp.usage << ' ' << tmp.flag << '\n';
int cur = b - (a < c ? a : n - 1 - a);// cerr << "cur = " << cur << '\n';
if (tmp.be <= cur && cur < tmp.en) {
tmp.usage += tmp.flag ? cur - tmp.be : 0;
if (tmp.cur == -inf) tmp.cur = cur;
}
else if (cur < tmp.be) {
if (tmp.cur == -inf) tmp.cur = tmp.be;
}
else {
tmp.usage += cur - tmp.en + 1 + (tmp.flag ? tmp.en - 1 - tmp.be : 0);
if (tmp.cur == -inf) tmp.cur = tmp.en - 1;
}
cout << tmp.usage + max(0, tmp.cur - (d - (a < c ? c : n - 1 - c) ) ) << '\n';
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
754 ms |
62488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
