#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6;
ll t[4 * N];
ll lz[4 * N];
void push(int v, int tl, int tr) {
if (!lz[v]) {
return;
}
t[v] += lz[v] * (tr - tl + 1);
if (tl != tr) {
lz[2 * v + 1] += lz[v];
lz[2 * v + 2] += lz[v];
}
lz[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int x) {
push(v, tl, tr);
if (l > tr || r < tl) {
return;
} else if (l <= tl && tr <= r) {
lz[v] += x;
push(v, tl, tr);
return;
} else {
int tm = (tl + tr) / 2;
upd(2 * v + 1, tl, tm, l, r, x);
upd(2 * v + 2, tm + 1, tr, l, r, x);
t[v] = t[2 * v + 1] + t[2 * v + 2];
}
}
ll get(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if (l > tr || r < tl) {
return 0;
} else if (l <= tl && tr <= r) {
return t[v];
} else {
int tm = (tl + tr) / 2;
return get(2 * v + 1, tl, tm, l, r) + get(2 * v + 2, tm + 1, tr, l, r);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector <int> h(n);
for (int i = 0; i < n; i++) {
cin >> h[i];
}
//upd(0, 0, N - 1, h[0], h[0], 1);
for (int i = 1; i < n; i++) {
upd(0, 0, N - 1, min(h[i], h[i - 1]), max(h[i], h[i - 1]), 1);
//upd(0, 0, N - 1, h[i], h[i], 1);
}
for (int it = 0; it < m; it++) {
int t;
cin >> t;
if (t == 1) {
int pos, val;
cin >> pos >> val;
pos--;
h[pos] = val;
} else {
int hg;
cin >> hg;
cout << get(0, 0, N - 1, hg, hg) << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
