#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e6 + 2;
const int inf = 2e9 + 2;
int st[4 * N], lzy[4 * N];
void Propagate(int node, int l, int r) {
if (lzy[node] == 0) return;
if (l < r) {
lzy[2 * node] += lzy[node];
lzy[2 * node + 1] += lzy[node];
}
st[node] += lzy[node];
lzy[node] = 0;
}
void Add(int node, int l, int r, int ql, int qr, int x) {
Propagate(node, l, r);
if (r < ql || qr < l || ql > qr) return;
if (ql <= l && r <= qr) {
lzy[node] += x;
Propagate(node, l, r);
return;
}
int mid = l + r >> 1;
Add(2 * node, l, mid, ql, qr, x);
Add(2 * node + 1, mid + 1, r, ql, qr, x);
st[node] = max(st[2 * node], st[2 * node + 1]);
}
int Get(int node, int l, int r, int x) {
Propagate(node, l, r);
if (l == r) return st[node];
int mid = l + r >> 1;
if (x <= mid) return Get(2 * node, l, mid, x);
else Get(2 * node + 1, mid + 1, r, x);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 1; i < n; i++) {
int manji = min(a[i - 1], a[i]);
int veci = max(a[i - 1], a[i]);
Add(1, 1, N, manji + 1, veci - 1, 1);
}
while (q--) {
int ty; cin >> ty;
if (ty == 2) {
int x; cin >> x;
cout << Get(1, 1, N, x) << en;
continue;
}
int i, manji, veci; cin >> i; i -= 1;
if (i > 0) {
manji = min(a[i - 1], a[i]);
veci = max(a[i - 1], a[i]);
Add(1, 1, N, manji + 1, veci - 1, -1);
}
if (i < n - 1) {
manji = min(a[i], a[i + 1]);
veci = max(a[i], a[i + 1]);
Add(1, 1, N, manji + 1, veci - 1, -1);
}
cin >> a[i];
if (i > 0) {
manji = min(a[i - 1], a[i]);
veci = max(a[i - 1], a[i]);
Add(1, 1, N, manji + 1, veci - 1, 1);
}
if (i < n - 1) {
manji = min(a[i], a[i + 1]);
veci = max(a[i], a[i + 1]);
Add(1, 1, N, manji + 1, veci - 1, 1);
}
}
return 0;
}
Compilation message
game.cpp: In function 'void Add(int, int, int, int, int, int)':
game.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid = l + r >> 1;
| ~~^~~
game.cpp: In function 'int Get(int, int, int, int)':
game.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid = l + r >> 1;
| ~~^~~
game.cpp:39:13: warning: control reaches end of non-void function [-Wreturn-type]
39 | else Get(2 * node + 1, mid + 1, r, x);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
