8,7 T 1ゲージ


 

#include 
#include 
using namespace std;
bool bo[100004]={0};
int a[100003];
int f[100030]={0};
int n,m;
int read()
{
	int neko=0,fu=1;
	char para=getchar();
	if(para =='-')fu=-1;
	while(para'9')para=getchar();
	while(para>='0'&¶<='9')
	{
	
		neko=neko*10+para-'0';
		para=getchar();
	}
	return neko *fu;
}
int main()
{
	//freopen("suffixes.in","r",stdin);
	//freopen("suffixes.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=n;i>=1;i--)
	{
		if(!bo[a[i]])
		{
			bo[a[i]]=1;
			f[i]=f[i+1]+1;
		}
		else f[i]=f[i+1];
	}
	for(int i=1;i<=m;i++)
	{
		int q=read();
		printf("%d
",f[q]);
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

入力ファイル:suffixes.in出力ファイル:suffixes.out時間制限:1 S空間制限:256 M題目はn個の数が順番に1列に並んでいることを記述し、m個の質問は、x番目の数からn番目の数まで何個の異なる数があるかを尋ねるたびに行われる.入力形式第1行入力n,m第2行入力n個数表示数列次m行,各行1個数表示問い合わせ出力形式出力共m行表示問い合わせ毎の回答サンプル入力10 10 1 2 3 4 4 100000 999 1 2 3 4 6 7 8 10
 
サンプル出力6 6 6 6 6 6 6 5 4 3 1データ範囲と約束20%データ、1<=n、m<=10 50%データ、1<=n、m<=10^3 100%データ、1<=n、m<=10^5、1<=10^5
これは水の問題で、ブール配列を逆順にシミュレーションすればいいです.の
2019.8.11更新:
数年後に自分の当初のブログを読み直して、自分がこの問題解を理解していないことに気づいたので、いくつかのものを補充しました.
これはゲージ関連試験のt 1であり、難易度は低い.最初は逆順列挙を思い浮かべることができますが、明らかに時間の複雑さが高いです.しかし、彼は数字の範囲を提供して、数字が大きくないため、私たちはバケツのソートのような思想を利用して、10^5のブール配列を開いて重さを調べることができて、次は簡単な線形ゲージでいいです.