概要
n 項からなる数列 a がある。
以下の様なクエリ ( l ) を m 個処理せよ。
- 位置 l 以降に何種類の値があるかを出力する
解法
位置 i 以降にある要素の集合は、位置 i + 1 以降にある要素の集合に を加えたものとです。
また、位置 n 以降にある要素の集合は明らかに空集合となります。
これらより、a を後ろから走査して set に加えていくことで、O( n log n ) であらゆるクエリに対する答えを前計算することができます。
この結果を使うと各クエリに O( 1 ) で答えることができます。
コード
typedef vector<int> VI; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( v, c ) for ( auto &v : c ) int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int n, m; cin >> n >> m; VI as( n ); FOR( a, as ) { cin >> a; } set<int> s; VI res( n ); for ( int i = n - 1; 0 <= i; i-- ) { s.insert( as[i] ); res[i] = s.size(); } REP( iteration, 0, m ) { int l; cin >> l; cout << res[ l - 1 ] << endl; } return 0; }