kmjp's blog

競技プログラミング参加記です

yukicoder : No.992 最長増加部分列の数え上げ

これどっかで出てそう。
https://yukicoder.me/problems/no/992

問題

整数列A[i]が与えられる。
この部分列のうち、元の整数列のLISとなるものは何通りか。
部分列の値が同じでも、抽出した位置が違う数列は別物とする。

解法

まず、各要素がLISを構築する際何要素目になるかを求めよう。
i番目の要素がLISに入るとするとf(i)番目に入るものとする。
どうLISを構築しても、各要素が来る位置が変わることはない。

次にLISの構築の仕方を考えるわけだが、仮にA[i]をLISに加える場合、その直前の要素jは、

  • j<i
  • A[j]<A[i]
  • f(j)+1=f(i)

でなければならない。
そのようなjに対し、A[0...(i-1)]の部分列のうちA[j]を末尾とするような組み合わせの総和がA[i]を末尾とするケースとなる。
これを求めるには、添え字順を変えたBITで累積和を求めればよい。
以下のように並べかえる。

  • f(x) < f(y)ならxが手前
  • f(x)==f(y)ならxとyの大きいほうの添え字が手前

こうすると上記総和を求める処理が数列中の区間和となるので、BITを利用できるようになる。

int N;
int A[202020],B[202020];
int ID[202020],IDnum[202020],IDs[202020];
int num[202020];
ll dp[202020];
int V[202020];
ll mo=1000000007;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;}
	void add(int e,V v) { e++; while(e<=1<<ME) (bit[e-1]+=v)%=mo,e+=e&-e;}
};
BIT<ll,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	V[0]=-1<<30;
	FOR(i,N) V[i+1]=1<<30;
	int ma=0;
	FOR(i,N) {
		cin>>A[i];
		x=lower_bound(V,V+N+1,A[i])-V;
		ID[i]=x;
		ma=max(ma,x);
		IDnum[i]=++num[x];
		V[x]=A[i];
	}
	IDs[1]=1;
	for(i=2;i<=ma;i++) IDs[i]=IDs[i-1]+num[i-1];
	B[0]=-1<<30;
	FOR(i,N) B[IDs[ID[i]]+num[ID[i]]-IDnum[i]]=A[i];
	ll ret=0;
	bt.add(0,1);
	FOR(i,N) {
		x=lower_bound(B+IDs[ID[i]-1],B+IDs[ID[i]],A[i])-B;
		x--;
		dp[i]=(bt(x)-bt(IDs[ID[i]-1]-1)+mo)%mo;
		if(ID[i]==ma) ret+=dp[i];
		bt.add(IDs[ID[i]]+num[ID[i]]-IDnum[i],dp[i]);
	}
	cout<<ret%mo<<endl;
}

まとめ

方針はすぐ思いついたけど割と手間取った。