fork download
copy 
  1.  #include<bits/stdc++.h>
  2. using  namespace std;
  3. #define  ll                       long long
  4. #define  pb                       push_back
  5. #define  lb                       lower_bound
  6. #define  ub                       upper_bound
  7. #define  fr                       first
  8. #define  sc                       second
  9. #define  memset( a, b )           memset( a, b , sizeof(a) )
  10. #define  PI                       3.1415926535897932384626
  11. #define  mod                        1000000007
  12. #define  rrep( i , n)            for( i=n-1 ; i>=0 ; i--)
  13. #define  rep( i , n )            for( i=0 ; i<n; i++ )
  14. #define  int_max                 1000000000000000000
  15.  
  16.  
  17.   int t ,d , ct  , q, ans ,l , r ,n ,m , mx, mn , i, j, k ,x , y , z , s  ;
  18.  
  19.  char ch;               
  20.  
  21.      int a[30003] , b[30003] ;         
  22.    int fre[200003] ;
  23.  
  24.   int blk = 550 ;
  25.  
  26. struct query{
  27.  
  28.     int i ; int l ; int r ;
  29.  
  30. };
  31.  
  32. query Q[200003] ;
  33.  
  34.  
  35. bool comp(query a , query b){
  36.  
  37.     if(a.l/blk != b.l/blk ) return a.l/blk < b.l/blk ;
  38.  
  39.     else return a.r <= b.r ;
  40.  
  41.  
  42. }
  43.  
  44.  
  45. void pluss(int idx){
  46.  
  47.    fre[a[idx]]++ ; 
  48.     if(fre[a[idx]] == 1) ct++ ;
  49.  
  50. }
  51.  
  52. void minuss(int idx){
  53.  
  54.     fre[a[idx]]-- ;
  55.     if(fre[a[idx]] == 0) ct-- ;
  56.  
  57.  
  58.  
  59. }
  60.  
  61. int main(){ 
  62.  
  63.  
  64.  
  65. cin>>n ;
  66. rep(i ,n) cin>>a[i] ;
  67.  
  68. cin>>q ;
  69.  
  70. rep(i ,q){
  71.  
  72. cin>>x>>y ;
  73.  
  74.     Q[i].i = i , Q[i].l = x -1 , Q[i].r = y -1 ;
  75.  
  76. }
  77.  
  78. sort(Q , Q + q , comp) ;
  79.  
  80.  
  81. int Start = 0 ,End = -1 ;
  82. rep(i , q){
  83.  
  84.  
  85.   l = Q[i].l ;
  86.   r = Q[i].r ;
  87.  
  88.    while(l < Start) Start-- , pluss(Start) ;
  89.    while(End < r) End++ , pluss(End) ;
  90.  
  91.    while(l > Start)   minuss(Start) , Start++ ;
  92.    while(End  > r) minuss(End) , End-- ;
  93.  
  94.  b[Q[i].i] = ct ;
  95. }
  96.  
  97.  
  98. rep(i , q) cout<<b[i]<<"\n";
  99.  
  100.  
  101. return 0;
  102. }
  103.  
  104.  
  105.  
  106.  
Success #stdin #stdout 0s 4336KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/SvaFck
language:
C++14 (gcc 8.3)
created:
3 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!