【洛谷2215】【HNOI 2007】上昇シーケンス

タイトルの説明
与えられたS={a 1,a 2,a 3,...,an}に対して、P={ax 1,ax 2,ax 3,...,axm}があれば、満足する(x 1
にゅうしゅつりょくけいしき
入力形式:
1行目はN個で、シーケンスが全部でN個の要素があることを示し、2行目はN個で、a 1,a 2,...,an 3行目はM個で、問い合わせ回数を表す.次に、M行の1行あたりの数Lと続き、長さLの立ち上がりシーケンスを尋ねることを示す.
出力フォーマット:
各問合せについて、対応するシーケンスが存在する場合は出力、そうでない場合はImpossibleを印刷する.
入出力サンプル
サンプル#1を入力:

6
3 4 1 2 3 6
3
6
4
5

出力サンプル#1:

Impossible
1 2 3 6
Impossible

説明
データ範囲N<=10000 M<=1000
問題解
データ範囲が10000なので、n^2のLISを求めるのは無理で、ツリー配列で最適化できますが、この問題はm回の問い合わせがあるので、以前のツリー配列のLISを求めるのとは違って、今回f[i]はiを先頭とするLISの長さ(辞書順最小(符号)であるため)を表し、樹状配列が求められないことを発見した.今回求めたのはそれより大きいmaxであるため、小さなテクニックを用いて樹状配列を逆さにし、iという数の位置がn-i+1になり、これで大きな数が前になり、小さい数が後になるので、接頭辞maxを求めることができる(とても巧みです).

#include
#include
#include
#include
using namespace std;
const int maxn=10010;
int n,m,k,a[maxn],b[maxn],c[maxn],ans[maxn],num;
int t[maxn],f[maxn];
int lowbit(int x){
	return x&(-x);
}
void add(int x,int y){
	x=n-x+1;
	for(int i=x;i<=n;i+=lowbit(i))
	t[i]=max(t[i],y);
}
int find(int x){
	x=n-x+1;//      ，      ，            max
	int ans=0;
	for(int i=x;i>=1;i-=lowbit(i))
	ans=max(t[i],ans);
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		c[i]=b[i]=a[i];
    }
	sort(b+1,b+n+1);
	num=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++){
		c[i]=lower_bound(b+1,b+num+1,c[i])-b;
	}

/* for(int i=1;i<=n;i++)
	cout<=1;i--){
		f[i]=find(c[i]+1)+1;
		add(c[i],f[i]);
		len=max(len,f[i]);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&k);
		if(k>len){
			printf("Impossible
");
		}
		else{
			last=0;
			for(int i=1;i<=n;i++)
			if(f[i]>=k&&a[i]>last){
				if(k==0) break;
				else{
					printf("%d ",a[i]);
					k--;
					last=a[i];
				}
			}
			printf("
");
		}
	}

	return 0;
}