#include "bits/stdc++.h"
using namespace std;
const int maxn = 2e6 + 6;
int n, q, h[maxn];
int mn[maxn], mx[maxn];
pair<int, int> a[maxn];
struct fenwick_tree {
#define gb(x) (x) & (-x)
int n;
vector<int> bit;
fenwick_tree() {}
fenwick_tree(int n) : n(n), bit(n + 5) {}
void update(int x, int val) {
if(x <= 0) return;
for(int i = x; i <= n; i += gb(i)) bit[i] += val;
}
int get(int x) {
int ans = 0;
for(int i = x; i > 0; i -= gb(i)) ans += bit[i];
return ans;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
} fen_mn, fen_mx;
void update(int p) {
fen_mx.update(mx[p], -1);
fen_mn.update(mn[p], -1);
mx[p] = max(a[p].first, a[p].second);
mn[p] = min(a[p].first, a[p].second);
fen_mx.update(mx[p], 1);
fen_mn.update(mn[p], 1);
}
void solve() {
cin >> n >> q;
for(int i = 1; i <= n; ++i) {
cin >> h[i];
}
for(int i = 1; i < n; ++i) {
a[i] = {h[i], h[i + 1]};
update(i);
}
fen_mx = fenwick_tree(maxn);
fen_mn = fenwick_tree(maxn);
while(q--) {
int op; cin >> op;
if(op == 1) {
int p, val; cin >> p >> val;
if(p < n) {
a[p].first = val;
update(p);
}
if(p > 1) {
a[p - 1].second = val;
update(p - 1);
}
}
else {
int height; cin >> height;
int x = n - 1 - fen_mn.get(height, maxn) - fen_mx.get(height);
cout << x << '\n';
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18012 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
18012 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18012 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
18012 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18012 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
18012 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
