fork download
  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
stdin
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3
stdout
3
2