#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 = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
int n , m ;
int g[4*N] , a[N] ;
void build ( int v , int l , int r , int x , int y ){
if ( l > y || r < x ) return ;
if ( ( x >= l && y <= r ) || l == r ){
g[v] ++ ;
return ;
}
int mid = ( l + r ) / 2 ;
build( v + v , l , mid , x , y ) ;
build ( v + v + 1 , mid + 1 , r , x , y ) ;
}
void del ( int v , int l , int r , int x , int y ){
if ( l > y || r < x ) return ;
if ( (x >= l && y <= r ) || l == r ){
g[v] -- ;
return ;
}
int mid = ( l + r ) / 2 ;
del( v + v , l , mid , x , y ) ;
del ( v + v + 1 , mid + 1 , r , x , y ) ;
}
int get ( int v , int l , int r , int x ){
if ( x < l || x > r ) return 0 ;
if ( l == r ) return g[v] ;
int sum = g[v] ;
int mid = ( l + r ) / 2 ;
if ( x < m ) sum += get( v + v , l , mid , x ) ;
else sum += get( v + v + 1 , mid + 1 , r , x ) ;
return sum ;
}
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]) ) ;
while ( m -- ){
int tt ;
cin >> tt ;
if ( tt == 1 ){
int pos , val ;
cin >> pos >> val ;
if ( pos > 1 ) del( 1 , 1 , n , min(a[pos-1],a[pos]) , max(a[pos-1],a[pos]) ) ;
if ( pos < n ) del( 1 , 1 , n , min(a[pos],a[pos+1]) , max(a[pos],a[pos+1]) ) ;
a[pos] = val ;
if ( pos > 1 ) build( 1 , 1 , n , min(a[pos-1],a[pos]) , max(a[pos-1],a[pos]) ) ;
if ( pos < n ) build( 1 , 1 , n , min(a[pos],a[pos+1]) , max(a[pos],a[pos+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 |
- |
