#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define Xiao ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define endl "\n"
const int N = 1e6 + 5 ;
const int mod = 1e9 + 7 ;
int n , m ;
int g[4*N] , a[N] , lz[4*N] ;
void push( int v , int l , int r ){
if ( !lz[v] ) return ;
if ( l != r ){
lz[v+v] += lz[v] ;
lz[v+v+1] += lz[v] ;
}
g[v] += (r-l+1)*lz[v] ;
lz[v] = 0 ;
}
void build ( int v , int l , int r , int x , int y , int val ){
push(v,l,r) ;
if ( l > y || r < x ) return ;
if ( ( x <= l && y >= r ) ){
lz[v] += val ;
push(v,l,r) ;
return ;
}
int mid = ( l + r ) / 2 ;
build( v + v , l , mid , x , y , val ) ;
build( v + v + 1 , mid + 1 , r , x , y , val ) ;
g[v] = g[v+v]+g[v+v+1] ;
}
int get ( int v , int l , int r , int x ){
push(v,l,r) ;
if ( x < l || x > r ) return 0 ;
if ( l == r ) return g[v] ;
int mid = ( l + r ) / 2 ;
if ( x <= mid ) return get( v + v , l , mid , x ) ;
else return get( v + v + 1 , mid + 1 , r , x ) ;
}
void solve(){
cin >> n >> m ;
for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
for ( int i = 1 ; i < n ; i ++ ) build( 1 , 1 , n , min(a[i],a[i+1]) , max(a[i],a[i+1]) , 1 ) ;
while ( m -- ){
int tt ;
cin >> tt ;
if ( tt == 1 ){
int pos , val ;
cin >> pos >> val ;
if ( pos > 1 ) build( 1 , 1 , n , min(a[pos-1],a[pos]) , max(a[pos-1],a[pos]) , -1 ) ;
if ( pos < n ) build( 1 , 1 , n , min(a[pos],a[pos+1]) , max(a[pos],a[pos+1]) , -1 ) ;
a[pos] = val ;
if ( pos > 1 ) build( 1 , 1 , n , min(a[pos-1],a[pos]) , max(a[pos-1],a[pos]) , 1 ) ;
if ( pos < n ) build( 1 , 1 , n , min(a[pos],a[pos+1]) , max(a[pos],a[pos+1]) , 1 ) ;
}
else{
int x ;
cin >> x ;
cout << get( 1 , 1 , n , x ) << endl ;
}
}
}
signed main(){
Xiao ;
int t = 1 ;
// cin >> t ;
while ( t -- )
solve() ;
}
Compilation message
game.cpp: In function 'void fopn(std::string)':
game.cpp:8:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:8:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
