#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
const int N = 1e5+1;
struct ST {
vi t;
ST(int nn) {
t.assign(4*nn+1,0);
}
void update(int node,int l,int r,int L,int R,int v) {
if (l > R || r < L) return;
if (l >= L && r <= R) {
t[node]+=v;
return;
}
int m = (l+r) >> 1;
update(2*node,l,m,L,R,v),update(2*node+1,m+1,r,L,R,v);
}
int query(int node,int l,int r,int p) {
if (l == r) return t[node];
int m = (l+r) >> 1;
if (p<=m) return t[node]+query(2*node,l,m,p);
else return t[node]+query(2*node+1,m+1,r,p);
}
}st(LIM);
void solve() {
int n,m;
cin >> n >> m;
vi h(n+1);
for (int i=1;i<=n;i++) cin >> h[i];
for (int i=1;i<n;i++) {
st.update(1,1,LIM,min(h[i],h[i+1]),max(h[i],h[i+1]),1);
}
while (m--) {
int type;
cin >> type;
if (type == 2) {
int x;
cin >> x;
cout << st.query(1,1,LIM,x) << '\n';
}else {
int p,v;
cin >> p >> v;
if (p>1) st.update(1,1,LIM,min(h[p-1],h[p]),max(h[p-1],h[p]),-1);
if (p<n) st.update(1,1,LIM,min(h[p],h[p+1]),max(h[p],h[p+1]),-1);
h[p] = v;
if (p>1) st.update(1,1,LIM,min(h[p-1],h[p]),max(h[p-1],h[p]),1);
if (p<n) st.update(1,1,LIM,min(h[p],h[p+1]),max(h[p],h[p+1]),1);
}
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef Dodi
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |