HR Nominating Group Leaders ( Mo's Algorithm, Sqrt Decomposition )

Programming Problems and Competitions :: HackerRank

題意：
N 個人排成一排，每個人對人投一個票。Q 筆詢問，問 [ L, R ] 中，是否有恰好得到 X 票的人，如果有，輸出其中編號最小的。

制約：
1 ≤ T ≤ 5
1 ≤ N, Q ≤ 1e5
N 的總和和 Q 的總和不超過 3e5。

解法：
顯然可以用莫隊，只是編號最小怎麼處理？
額外維護一個二維陣列：
cnt_freq[ i ][ j ]：編號在 [ i * BS, ( i + 1 ) * BS ) 中的人裡，當前有 j 票的人數。
有了這個，在 N^0.5 的時間內找到答案是在哪一個塊裡，接著再花費 N^0.5 的時間線性搜尋塊裡的元素。

時間 / 空間複雜度：
O( ( N + Q ) ^ 1.5 )

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

const int MAXN = int( 1e5 );
const int MAXQ = int( 1e5 );
const int BS = 350;

int N;
int V[ MAXN ];
int Q;
int L[ MAXQ ], R[ MAXQ ], X[ MAXQ ];
int qord[ MAXQ ];

int freq[ MAXN ];
int cnt_freq[ BS ][ MAXN + 1 ];

int ans[ MAXQ ];

signed main() {
  ios::sync_with_stdio( 0 );
  int T;
  cin >> T;
  for( int ti = 0; ti < T; ++ti ) {
    cin >> N;
    for( int i = 0; i < N; ++i ) {
      cin >> V[ i ];
    }
    cin >> Q;
    for( int i = 0; i < Q; ++i ) {
      cin >> L[ i ] >> R[ i ] >> X[ i ];
      qord[ i ] = i;
    }
    sort( qord, qord + Q, [ & ]( int i, int j ) {
            if( L[ i ] / BS != L[ j ] / BS ) return L[ i ] / BS < L[ j ] / BS;
            return R[ i ] < R[ j ]; } );
    memset( freq, 0, sizeof( freq ) );
    memset( cnt_freq, 0, sizeof( cnt_freq ) );
    memset( ans, -1, sizeof( ans ) );
    for( int qi = 0, lb = 1, rb = 0; qi < Q; ++qi ) {
      int ql = L[ qord[ qi ] ];
      int qr = R[ qord[ qi ] ];
      int qx = X[ qord[ qi ] ];
      while( ql < lb ) {
        --lb;
        --cnt_freq[ V[ lb ] / BS ][ freq[ V[ lb ] ] ];
        ++freq[ V[ lb ] ];
        ++cnt_freq[ V[ lb ] / BS ][ freq[ V[ lb ] ] ];
      }
      while( lb < ql ) {
        --cnt_freq[ V[ lb ] / BS ][ freq[ V[ lb ] ] ];
        --freq[ V[ lb ] ];
        ++cnt_freq[ V[ lb ] / BS ][ freq[ V[ lb ] ] ];
        ++lb;
      }
      while( rb < qr ) {
        ++rb;
        --cnt_freq[ V[ rb ] / BS ][ freq[ V[ rb ] ] ];
        ++freq[ V[ rb ] ];
        ++cnt_freq[ V[ rb ] / BS ][ freq[ V[ rb ] ] ];
      }
      while( qr < rb ) {
        --cnt_freq[ V[ rb ] / BS ][ freq[ V[ rb ] ] ];
        --freq[ V[ rb ] ];
        ++cnt_freq[ V[ rb ] / BS ][ freq[ V[ rb ] ] ];
        --rb;
      }
      for( int bi = 0; bi <= ( N - 1 ) / BS; ++bi ) {
        if( cnt_freq[ bi ][ qx ] ) {
          for( int i = bi * BS; i < ( bi + 1 ) * BS; ++i ) {
            if( freq[ i ] == qx ) {
              ans[ qord[ qi ] ] = i;
              break;
            }
          }
          break;
        }
      }
    }
    for( int i = 0; i < Q; ++i ) {
      cout << ans[ i ] << "\n";
    }
  }
  return 0;
}