Codeforces ECR #066 : F. The Number of Subpermutations

これは勉強になった。
https://codeforces.com/contest/1175/problem/F

問題

整数列Aが与えられる。
この部分列のうち、1～|部分列数|のPermutationとなるものは何通りか。

解法

まずPermutationの判定法から。
数列の値1～Nに対し、大きな乱数を割り当てよう。値vに対応する乱数をP[v]とする。
この数列をxorを用いた部分列を考える。
要素数kの部分列がPermutationであるならば、そのxorを取った値はP[1] xor P[2] xor ... xor P[k]となる。
すなわち累積和のxor版を用いることで判定できるようになる。

要素数1の部分列が条件を満たすのはA[i]=1だけの1要素であるのは明らか。
以下、部分列が2要素以上のPermutationを成すとして、最大値がA[i]=1より後ろに来るケースを考える。（後で同様に手前に来るケースを処理する）
A[i]=1とし、A[i+1]、A[i+2]…A[j]...を順に右端の候補として総当たりしていく。途中A[j]=1となるjが来たら終了する。

今A[i]=1を含み、A[j]を右端とするケースを考える。
p=max(A[i...j])とすると、この数列長はpなのでA[j-p+1]～A[j]がPermutationでなければならない。
これは先ほどの累積和を用いて高速に判定できる。

int N;
int A[303030];

pair<ll,ll> H[303030];
pair<ll,ll> HS[303030];
pair<ll,ll> S[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	mt19937 mt(time(0));
	
	for(i=1;i<=300000;i++) {
		H[i].first=HS[i].first=mt();
		H[i].second=HS[i].second=mt();
		HS[i].first^=HS[i-1].first;
		HS[i].second^=HS[i-1].second;
	}
	
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	ll ret=0;
	
	FOR(x,2) {
		FOR(i,N) {
			S[i+1].first=S[i].first^H[A[i]].first;
			S[i+1].second=S[i].second^H[A[i]].second;
		}
		FOR(i,N) if(A[i]==1) {
			int ma=0;
			for(j=i+1;j<N;j++) {
				if(A[j]==1) break;
				ma=max(ma,A[j]);
				if(j>=ma-1) {
					if((S[j+1].first^S[j+1-ma].first)==HS[ma].first && (S[j+1].second^S[j+1-ma].second)==HS[ma].second) ret++;
				}
			}
		}
		reverse(A,A+N);
	}
	FOR(i,N) if(A[i]==1) ret++;
	
	cout<<ret<<endl;
}

まとめ

順番を無視するために乱数のxorを使うのも、最大値に着目するのも思いつかなかった…。