CFR 220 B. Little Elephant and Array ( Mo's Algorithm )

Problem - B - Codeforces

題意：
給 N 個元素的序列，M 筆詢問，問考慮 A[ L, R ] 有多少不同的數字 A[ x ] 出現恰好 A[ x ] 次。

資料規模：
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 1e5) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a1, a2, ..., an (1 ≤ ai ≤ 1e9). Next m lines contain descriptions of queries, one per line. The j-th of these lines contains the description of the j-th query as two space-separated integers lj and rj (1 ≤ lj ≤ rj ≤ n).

解法：
莫隊水過。map 太慢要用 unordered_map。

時間 / 空間複雜度：
O( N lg N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e5;
const int MAXM = ( int ) 1e5;
const int BSZ = 400;

int N, M;
int A[ MAXN ];
int L[ MAXM ], R[ MAXM ];
int ord[ MAXM ];
int ans[ MAXM ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
  for( int i = 0; i < M; ++i ){
    cin >> L[ i ] >> R[ i ];
    --L[ i ], --R[ i ];
    ord[ i ] = i;
  }
  sort( ord, ord + M, [ & ]( int i, int j ){
          if( L[ i ] / BSZ != L[ j ] / BSZ ) return L[ i ] / BSZ < L[ j ] / BSZ;
          return R[ i ] < R[ j ];
        } );
  for( int f = 0, lb = 0, rb = -1; f < M; ++f ){
    static unordered_map< int, int > cnt;
    static int val = 0;
    int i = ord[ f ];
    while( L[ i ] < lb ){
      --lb;
      if( cnt[ A[ lb ] ] != A[ lb ] and cnt[ A[ lb ] ] + 1 == A[ lb ] ){
        ++val;
      } else if( cnt[ A[ lb ] ] == A[ lb ] ){
        --val;
      }
      ++cnt[ A[ lb ] ];
    }
    while( lb < L[ i ] ){
      if( cnt[ A[ lb ] ] == A[ lb ] ){
        --val;
      } else if( cnt[ A[ lb ] ] - 1 == A[ lb ] ){
        ++val;
      }
      --cnt[ A[ lb ] ];
      ++lb;
    }
    while( rb < R[ i ] ){
      ++rb;
      if( cnt[ A[ rb ] ] != A[ rb ] and cnt[ A[ rb ] ] + 1 == A[ rb ] ){
        ++val;
      } else if( cnt[ A[ rb ] ] == A[ rb ] ){
        --val;
      }
      ++cnt[ A[ rb ] ];
    }
    while( R[ i ] < rb ){
      if( cnt[ A[ rb ] ] == A[ rb ] ){
        --val;
      } else if( cnt[ A[ rb ] ] - 1  == A[ rb ] ){
        ++val;
      }
      --cnt[ A[ rb ] ];
      --rb;
    }
    ans[ i ] = val;
  }
  for( int i = 0; i < M; ++i ){
    cout << ans[ i ] << "\n";
  }
  return 0;
}