fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
  5. #define ll long long
  6. #define ld long double
  7. #define pb push_back
  8. #define fe first
  9. #define se second
  10. #define nl "\n"
  11. #define pp pair < ll , ll > 
  12. #define sz(x) (ll)x.size()
  13. #define st(x) sort(x.begin(),x.end())
  14. #define rst(x) sort(x.rbegin(), x.rend())
  15. #define all(x) x.begin(),x.end()
  16. long double pi = 3.14159265358979323;
  17.  
  18. const double EPS = 1e-12;
  19. const int N = 6*1e5 + 10;
  20. const int mod = 1e9 + 7;
  21.  
  22. int BIT[ 4 * N ] ; 
  23.  
  24. void update( int pos, int val ){
  25.   while( pos < N ){
  26.     BIT[ pos ] += val ;
  27.     pos += ( pos & -pos ) ;
  28.   }
  29. }
  30.  
  31. int query( int pos ){
  32.   int ans( 0 ) ;
  33.   while( pos ){
  34.     ans += BIT[ pos ] ;
  35.     pos -= ( pos & -pos ) ;
  36.   }
  37.   return ans ;
  38. }
  39.  
  40. struct query{
  41.    char t ;
  42.    int l, r ;
  43. }qrr[ N ] ;
  44.  
  45. int ar[ N ] ;
  46. vector< int > v ;
  47. map< int, int > mpp ;
  48.  
  49. int main()
  50. {
  51.     fast;
  52.  
  53.     int n, q ;
  54.     cin >> n >> q ;
  55.  
  56.     for( int i = 1 ; i <= n ; i++ ){
  57.       cin >> ar[ i ] ;
  58.       v.pb( ar[i] );
  59.     }
  60.  
  61.     for( int i = 0 ; i < q ; i++ ){
  62.       cin >> qrr[ i ].t >> qrr[ i ].l >> qrr[ i ].r ;
  63.          v.pb( qrr[ i ].r ) ;
  64.          v.pb( qrr[ i ].l ) ;
  65.     }
  66.  
  67.    int ind( 2 ) ;
  68.    sort( all( v ) ) ;
  69.    mpp[ v[ 0 ] ] = 1 ;
  70.    for( int i = 1 ; i < sz( v ) ; i++ ){
  71.     if( v[ i ] != v[ i - 1 ] )
  72.       mpp[ v[ i ] ] = ind++ ;
  73.    }
  74.  
  75.    for( int i = 1 ; i <= n ; i++ ){
  76.       int pos = mpp[ ar[ i ] ] ;
  77.       ar[ i ] = pos ;
  78.       update( pos, 1 ) ;
  79.    }
  80.    for( int i = 0 ; i < q ; i++ ){
  81.       char t = qrr[ i ].t ;
  82.       int l = qrr[ i ].l ;
  83.       int r = qrr[ i ].r ;
  84.       if( t == '?' ){
  85.          l = mpp[ l ] ;
  86.          r = mpp[ r ] ;
  87.          cout << query( r ) - query( l - 1 ) << '\n' ;
  88.       }
  89.       else{
  90.          int prev = ar[ l ] ;
  91.          update( prev, -1 ) ;
  92.          r = mpp[ r ] ;
  93.          update( r, 1 ) ;
  94.          ar[ l ] = r ;
  95.       }
  96.    }
  97. }
Success #stdin #stdout 0s 4308KB
comments (?)
stdin
copy 
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3
stdout
copy 
3
2
https://ideone.com/KFwzlf
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!