Yuki 6 使いものにならないハッシュ ( Deque )

題意：
給 L, R，代表所求區間 [ L, R ] 中，如程式碼中的 get_hash() 函數，最長區間 [ l, r ] 滿足 get_hash( i | l ≤ i ≤ r ) 皆相異，其最大可能的 l。

資料規模：
L, R ≤ 2e5

解法：
用 deque，從後面掃回來，每次遇到碰撞就從 deque 的後面 pop 出來。

時間 / 空間複雜度：
O( R )

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

int get_hash( int v ){
  if( v < 10 )
    return v;
  int u = 0;
  while( v )
    u += v % 10, v /= 10;
  return get_hash( u );
}

signed main(){
  int L, R; cin >> L >> R;
  vector< int > cnt( 10 );
  deque< int > dq;
  int maxlen = 0, ans = -1;
  for( int i = R; i >= L; --i ){
    int ng = i == 1;
    for( int j = 2; j * j <= i; ++j )
      ng |= i % j == 0;
    if( ng ) continue;
    int hv = get_hash( i );
    while( cnt[ hv ] )
      --cnt[ dq.back() ], dq.pop_back();
    ++cnt[ hv ], dq.emplace_front( hv );
    if( maxlen < dq.size() )
      maxlen = dq.size(), ans = i;
  }
  cout << ans << endl;
  return 0;
}