torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Codeforces #215, Division 2, B : Sereja and Suffixes

概要

n 項からなる数列 a がある。
以下の様なクエリ ( l ) を m 個処理せよ。

  • 位置 l 以降に何種類の値があるかを出力する

解法

位置 i 以降にある要素の集合は、位置 i + 1 以降にある要素の集合に a_i を加えたものとです。
また、位置 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;
}