#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 = 400;
const int MAX_N = 3e5 + 5;
int nx[MAX_N][2];
pair<ll, int> dp[MAX_N][2];
pair<int, int> dq[2 * block + 1];
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 = block, dr = block;
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][1]);
if (rangesl[bl][i - a] < rangesr[bl][i - a]) {
chkmin(sz[bl], i - a);
}
}
// sz[bl]--;
}
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], a = nx[a][0];
else if (b > ran[a][1]) ans += b - ran[a][1], b = ran[a][1], a = nx[a][1];
else a++;
}
while (a + block < c) {
int bl = a / block;
if (b > rangesr[bl][sz[bl] - 1]) {
ans += max<ll>(0, b - rangesr[bl][sz[bl] - 1]);
b = dp[a + sz[bl]][1].y;
} else if (b < rangesl[bl][sz[bl] - 1]) {
b = rangesl[bl][sz[bl] - 1];
}
int i = a + sz[bl];
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;
}
}
// 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;
a += block;
}
while (a < c) {
if (b < ran[a][0]) b = ran[a][0], a = nx[a][0];
else if (b > ran[a][1]) ans += b - ran[a][1], b = ran[a][1], a = nx[a][1];
else 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() {
ios_base::sync_with_stdio(false);
cin.tie(0);
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 + 1 < 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 + 1 < n; i += block) {
Update(i, min(i + block, n - 1));
}
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 - 1, a[i] / block * block + block));
} 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++) {
if (t[i] == 1) a[i] = n - 2 - a[i];
else a[i] = n - 1 - a[i], c[i] = n - 1 - c[i];
}
}
for (int i = 0; i < q; i++) {
if (t[i] == 2) cout << ans[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 2 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 3 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 4 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 5 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 6 |
Correct |
3 ms |
16888 KB |
Output is correct |
| 7 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 8 |
Correct |
3 ms |
16720 KB |
Output is correct |
| 9 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 10 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 11 |
Incorrect |
7 ms |
16720 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
841 ms |
31304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 2 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 3 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 4 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 5 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 6 |
Correct |
3 ms |
16888 KB |
Output is correct |
| 7 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 8 |
Correct |
3 ms |
16720 KB |
Output is correct |
| 9 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 10 |
Correct |
2 ms |
16720 KB |
Output is correct |
| 11 |
Incorrect |
7 ms |
16720 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
