#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int mod = 998244353;
const int sz = 3e5+5; /// mind the sz
/*struct BIT{
vl e;
void init(ll n){
e.assign(n+1, -1);
}
ll base(ll x){
if(e[x] < 0){
return x;
}
return e[x] = base(e[x]);
}
bool unite(ll a, ll b){
a = base(a);
b = base(b);
if(a == b){return false;}
if(e[a] > e[b]){swap(a, b);}
}
};*/
struct Segtree{
vl st, lazy;
void init(ll n){
st.assign(n << 2, 0);
lazy.assign(n << 2, 0);
}
void push(ll v, ll l, ll r){
if(l == r || !lazy[v]){return ;}
lazy[v*2] += lazy[v];
lazy[v*2+1] += lazy[v];
ll m = (l + r) >> 1;
st[v*2] += ((m - l + 1) * lazy[v]);
st[v*2+1] += ((r - m) * lazy[v]);
lazy[v] = 0;
}
void update(ll v, ll tl, ll tr, ll l, ll r, ll val){
if(tl > r || tr < l){return ;}
if(tl >= l && tr <= r){
lazy[v] += val;
st[v] += ((tr - tl + 1) * val);
return ;
}
push(v, tl, tr);
ll tm = (tl + tr) >> 1;
update(v*2, tl, tm, l, r, val);
update(v*2+1, tm+1, tr, l, r, val);
st[v] = st[v*2] + st[v * 2 + 1];
}
ll get(ll v, ll tl, ll tr, ll pos){
if(tl > pos || tr < pos){return 0;}
if(tl == tr){
return st[v];
}
push(v, tl, tr);
ll tm = (tl + tr)>>1;
if(pos <= tm){
return get(v*2, tl, tm, pos);
}
else{
return get(v*2+1, tm + 1, tr, pos);
}
}
};
void solve()
{
Segtree st;
ll n, m, i, j, type, l, r, pos, val;
cin>>n>>m;
st.init(1e6);
vl h(n+1);
for(i=1;i<=n;i++){
cin>>h[i];
}
for(i=1;i<n;i++){
st.update(1, 1, n, min(h[i], h[i+1]), max(h[i], h[i+1]), 1);
}
for(i=1;i<=m;i++){
cin>>type;
if(type == 1){
cin >> pos >> val;
if(pos > 1){
st.update(1, 1, n, min(h[pos], h[pos-1]), max(h[pos], h[pos-1]), -1);
st.update(1, 1, n, min(val, h[pos-1]), max(val, h[pos-1]), 1);
}
if(pos != n){
st.update(1, 1, n, min(h[pos], h[pos+1]), max(h[pos], h[pos+1]), -1);
st.update(1, 1, n, min(val, h[pos + 1]), max(val, h[pos + 1]), 1);
}
h[pos] = val;
}
else{
cin >> pos;
cout << st.get(1, 1, n, pos) << endl;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//precomp();
ll tst=1;
//cin>>tst;
while(tst--){
solve();
}
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
ok.
*/
Compilation message
game.cpp: In function 'void solve()':
game.cpp:82:17: warning: unused variable 'j' [-Wunused-variable]
82 | ll n, m, i, j, type, l, r, pos, val;
| ^
game.cpp:82:26: warning: unused variable 'l' [-Wunused-variable]
82 | ll n, m, i, j, type, l, r, pos, val;
| ^
game.cpp:82:29: warning: unused variable 'r' [-Wunused-variable]
82 | ll n, m, i, j, type, l, r, pos, val;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
63064 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
63068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
63064 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
63068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
63064 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
63068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
