#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int M = 4*N;
int n, m;
int node[M], lazy[M], nums[N];
void propagate(int head) {
if (lazy[head] == 0) return;
int val = lazy[head];
lazy[head] = 0;
node[head*2+1] += val;
lazy[head*2+1] += val;
node[head*2+2] += val;
lazy[head*2+2] += val;
}
void update(int l, int r, int L, int R, int val, int head) {
if (l > R || L > r) return;
if (L <= l && r <= R) {
node[head] += val;
lazy[head] += val;
return;
}
propagate(head);
int mid = (l+r)>>1;
update(l, mid, L, R, val, head*2+1);
update(mid+1, r, L, R, val, head*2+2);
node[head] = node[head*2+1] + node[head*2+2];
}
int query(int l, int r, int id, int head) {
if (l == r) return node[head];
propagate(head);
int mid = (l+r)>>1;
if (id <= mid) return query(l, mid, id, head*2+1);
return query(mid+1, r, id, head*2+2);
}
signed main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> nums[i];
for (int i = 2; i <= n; i++) {
int st = nums[i-1], end = nums[i];
if (st > end) swap(st, end);
if (st != end) update(0, N, st+1, end-1, 1, 0);
}
// for (int j = 1; j <= 10; j++) cout << query(0, N, j, 0) << " \n"[j==10];
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a;
if (a == 1) {
cin >> a >> b;
if (a - 1 > 0) {
int st = nums[a-1], end = nums[a];
if (st > end) swap(st, end);
if (st != end) update(0, N, st+1, end-1, -1, 0);
}
if (a + 1 <= n) {
int st = nums[a], end = nums[a+1];
if (st > end) swap(st, end);
if (st != end) update(0, N, st+1, end-1, -1, 0);
}
nums[a] = b;
if (a - 1 > 0) {
int st = nums[a-1], end = nums[a];
if (st > end) swap(st, end);
if (st != end) update(0, N, st+1, end-1, 1, 0);
}
if (a + 1 <= n) {
int st = nums[a], end = nums[a+1];
if (st > end) swap(st, end);
if (st != end) update(0, N, st+1, end-1, 1, 0);
}
// for (int j = 1; j <= 10; j++) cout << query(0, N, j, 0) << " \n"[j==10];
} else {
cin >> a;
cout << query(0, N, a, 0) << '\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
14636 KB |
Output is correct |
3 |
Correct |
8 ms |
14412 KB |
Output is correct |
4 |
Correct |
9 ms |
14668 KB |
Output is correct |
5 |
Correct |
8 ms |
14744 KB |
Output is correct |
6 |
Correct |
8 ms |
14624 KB |
Output is correct |
7 |
Correct |
6 ms |
12748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
14636 KB |
Output is correct |
3 |
Correct |
8 ms |
14412 KB |
Output is correct |
4 |
Correct |
9 ms |
14668 KB |
Output is correct |
5 |
Correct |
8 ms |
14744 KB |
Output is correct |
6 |
Correct |
8 ms |
14624 KB |
Output is correct |
7 |
Correct |
6 ms |
12748 KB |
Output is correct |
8 |
Correct |
48 ms |
1756 KB |
Output is correct |
9 |
Correct |
154 ms |
19296 KB |
Output is correct |
10 |
Correct |
126 ms |
19508 KB |
Output is correct |
11 |
Correct |
38 ms |
1596 KB |
Output is correct |
12 |
Correct |
77 ms |
3232 KB |
Output is correct |
13 |
Correct |
100 ms |
19228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
14636 KB |
Output is correct |
3 |
Correct |
8 ms |
14412 KB |
Output is correct |
4 |
Correct |
9 ms |
14668 KB |
Output is correct |
5 |
Correct |
8 ms |
14744 KB |
Output is correct |
6 |
Correct |
8 ms |
14624 KB |
Output is correct |
7 |
Correct |
6 ms |
12748 KB |
Output is correct |
8 |
Correct |
48 ms |
1756 KB |
Output is correct |
9 |
Correct |
154 ms |
19296 KB |
Output is correct |
10 |
Correct |
126 ms |
19508 KB |
Output is correct |
11 |
Correct |
38 ms |
1596 KB |
Output is correct |
12 |
Correct |
77 ms |
3232 KB |
Output is correct |
13 |
Correct |
100 ms |
19228 KB |
Output is correct |
14 |
Correct |
256 ms |
19304 KB |
Output is correct |
15 |
Correct |
323 ms |
19292 KB |
Output is correct |
16 |
Correct |
268 ms |
19240 KB |
Output is correct |
17 |
Correct |
258 ms |
19364 KB |
Output is correct |
18 |
Correct |
239 ms |
19364 KB |
Output is correct |