#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME (1.0 * clock() / CLOCKS_PER_SEC)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e6 + 5;
const int oo = 1e9, mod = 1e9 + 7;
int n, m, k, a[N], q;
struct Node{
int lazy;
int val;
} nodes[N*4];
void down(int id) {
int t=nodes[id].lazy;
nodes[id*2].lazy+=t;
nodes[id*2].val+=t;
nodes[id*2+1].lazy+=t;
nodes[id*2+1].val+=t;
nodes[id].lazy=0;
}
void update(int id, int l, int r, int u, int v, int val) {
if (v < l || r < u) {
return;
}
if (u <= l && r <= v) {
nodes[id].val += val;
nodes[id].lazy += val;
return;
}
int mid = (l + r) / 2;
down(id);
update(id*2, l, mid, u, v, val);
update(id*2+1, mid+1, r, u, v, val);
nodes[id].val = (nodes[id*2].val+nodes[id*2+1].val);
}
int get(int id, int l, int r, int u, int v) {
if (u>r || v<l /*|| l>r || u>v*/) return 0;
if (l>=u && r<=v) return nodes[id].val;
down(id);
int mid=(l+r)/2;
return (get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v));
}
void process() {
cin >> n >> q;
foru(i,1,n) cin >> a[i];
foru(i,2,n) {
int lo=min(a[i-1], a[i]);
int hi=max(a[i-1], a[i]);
update(1,1,N,lo,hi,1);
}
while (q--) {
int type; cin >> type;
if (type==1) {
int pos, val; cin >> pos >> val;
// update
int lo, hi;
if (pos==n) {
lo=min(a[pos], a[pos-1]);
hi=max(a[pos-1], a[pos]);
update(1,1,N,lo,hi,-1);
a[pos]=val;
lo=min(a[pos], a[pos-1]);
hi=max(a[pos-1], a[pos]);
update(1,1,N,lo,hi,1);
continue;
}
if (pos==1) {
lo=min(a[pos], a[pos+1]);
hi=max(a[pos], a[pos+1]);
update(1,1,N,lo,hi,-1);
a[pos]=val;
lo=min(a[pos], a[pos+1]);
hi=max(a[pos], a[pos+1]);
update(1,1,N,lo,hi,1);
continue;
}
// left
lo=min(a[pos], a[pos-1]);
hi=max(a[pos], a[pos-1]);
update(1,1,N,lo,hi,-1);
a[pos]=val;
lo=min(a[pos], a[pos-1]);
hi=max(a[pos], a[pos-1]);
update(1,1,N,lo,hi,1);
// right
lo=min(a[pos], a[pos+1]);
hi=max(a[pos], a[pos+1]);
update(1,1,N,lo,hi,-1);
a[pos]=val;
lo=min(a[pos], a[pos+1]);
hi=max(a[pos], a[pos+1]);
update(1,1,N,lo,hi,1);
continue;
} else {
int height; cin >> height;
// query
cout << get(1,1,N,height,height) << '\n';
}
}
return;
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
process();
cerr << "Time elapsed: " << __TIME << " s.\n";
return 0;
}
// dont stop
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
19036 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
19036 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
19036 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
