#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#define int ll
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
const int block = 650;
const int MAX_N = 3e5 + 5;
int nx[MAX_N][2];
pii dp[MAX_N][2];
pii dq[MAX_N];
int rangesl[MAX_N / block + 1][block];
int rangesr[MAX_N / block + 1][block];
int ran[MAX_N][2];
int sz[MAX_N / block + 1];
void Update(int a, int b) {
int dl = 1000, dr = 1000;
for (int i = a; i < b; i++) {
while (dl < dr) {
if (ran[dq[dl].x][dq[dl].y] < ran[i][0]) {
nx[dq[dl].x][dq[dl].y] = i;
dl++;
} else if (ran[dq[dr - 1].x][dq[dr - 1].y] > ran[i][1]) {
nx[dq[dr - 1].x][dq[dr - 1].y] = i;
dr--;
} else break;
}
dq[--dl] = {i, 0}, dq[dr++] = {i, 1};
}
while (dl < dr) {
nx[dq[dl].x][dq[dl].y] = b;
dl++;
}
for (int i = b - 1; i >= a; i--) {
for (int j = 0; j < 2; j++) {
int x = nx[i][j];
if (x == b) {
dp[i][j] = {0, ran[i][j]};
} else {
if (ran[i][j] > ran[x][1]) {
dp[i][j] = {dp[x][1].x + ran[i][j] - ran[x][1], dp[x][1].y};
} else {
dp[i][j] = {dp[x][0].x, dp[x][0].y};
}
}
}
}
int bl = a / block;
sz[bl] = b - a;
rangesl[bl][0] = ran[a][0];
rangesr[bl][0] = ran[a][1];
for (int i = a + 1; i < b; i++) {
rangesl[bl][i - a] = max(rangesl[bl][i - a - 1], ran[i][0]);
rangesr[bl][i - a] = min(rangesr[bl][i - a - 1], ran[i][0]);
}
}
ll Query(int a, int b, int c, int d) {
ll ans = 0;
while (a < c && a % block) {
if (b < ran[a][0]) b = ran[a][0];
else if (b > ran[a][1]) ans += b - ran[a][1], b = ran[a][1];
a++;
}
while (a + block < c) {
int bl = a / block;
int i = min(lower_bound(rangesl[bl], rangesl[bl] + sz[bl], b) - rangesl[bl],
lower_bound(rangesr[bl], rangesr[bl] + sz[bl], b, greater<int>()) - rangesr[bl]) + a;
if (i < a + block) {
if (b < ran[i][0]) {
ans += dp[i][0].x;
b = dp[i][0].y;
} else if (b > ran[i][1]) {
ans += dp[i][1].x;
ans += b - ran[i][1];
b = dp[i][1].y;
}
}
a += block;
}
while (a < c) {
if (b < ran[a][0]) b = ran[a][0];
else if (b > ran[a][1]) ans += b - ran[a][1], b = ran[a][1];
a++;
}
return ans + max<ll>(0, b - d);
}
int L[MAX_N], R[MAX_N], t[MAX_N], a[MAX_N], b[MAX_N], c[MAX_N], d[MAX_N];
ll ans[MAX_N];
int32_t main() {
int n, q;
cin >> n >> q;
for (int i = 0; i + 1 < n; i++) cin >> L[i] >> R[i];
for (int i = 0; i < q; i++) {
cin >> t[i] >> a[i] >> b[i] >> c[i];
if (t[i] == 2) cin >> d[i];
}
for (int i = 0; i < q; i++) a[i]--, c[i]--;
for (int i = 0; i < n; i++) R[i]--;
for (int ti = 0; ti < 2; ti++) {
for (int i = 0; i + 1 < n; i++) ran[i][0] = L[i] - i, ran[i][1] = R[i] - i;
for (int i = 0; i < n; i += block) {
Update(i, min(i + block, n));
}
for (int i = 0; i < q; i++) {
if (t[i] == 1) {
ran[a[i]][0] = b[i] - a[i], ran[a[i]][1] = c[i] - a[i];
Update(a[i] / block * block, min(n, a[i] / block * (block + 1)));
} else {
if (a[i] <= c[i]) ans[i] = Query(a[i], b[i] - a[i], c[i], d[i] - c[i]);
}
}
reverse(L, L + n - 1), reverse(R, R + n - 1);
for (int i = 0; i < q; i++) {
a[i] = n - 1 - a[i];
if (t[i] == 2) c[i] = n - 1 - c[i];
}
}
for (int i = 0; i < q; i++) {
if (t[i] == 2) cout << ans[i] << '\n';
}
// for (int i = 0; i < n; i++) l[i] = L[i], r[i] = R[i];
// for (int i = 0; i < q; i++) {
// if (t[i] == 1) {
// l[a[i]] = b[i], r[a[i]] = c[i];
// continue;
// }
// if (a[i] <= c[i]) {
// ll ti = b[i], ans = 0;
// for (int j = a[i]; j < c[i]; j++) {
// if (ti < l[j]) ti = l[j];
// else if (ti > r[j]) ans += ti - r[j], ti = r[j];
// ti++;
// }
// ans += max<ll>(0, ti - d[i]);
// cout << ans << '\n';
// } else {
// ll ti = b[i], ans = 0;
// for (int j = a[i] - 1; j >= c[i]; j--) {
// if (ti < l[j]) ti = l[j];
// else if (ti >= r[j]) ans += ti - r[j], ti = r[j];
// ti++;
// }
// ans += max<ll>(0, ti - d[i]);
// cout << ans << '\n';
// }
// }
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
26960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2527 ms |
64588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
26960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
