Codeforces #902 : Div1 D. Lexichromatography

意外とコード短め？
https://codeforces.com/contest/1876/problem/D

問題

整数列Aが与えられる。
この数列を、二つの部分列B,Rに分割するやり方のうち、以下を満たすのは何通りか。

• BはRより辞書順で小さい
• Aの部分列において、同じ値は、BとRに振り分けられた値の登場頻度の差が1以下でなければならない。

解法

後者の条件については、同じ値はRBRB...と振り分けるかBRBR...と振り分けるかの2択である。
よって登場する色数がcなら、後者の条件を満たすのは2^c通りである。

この範囲で、以下の3通りを考える。

• BはRより辞書順で小さい
• BはRより辞書順で大きいさい
• BとRは等しい

上2つの数は一致するので、求める値は2^cから等しいケースを引き、2で割ればよい。

int N;
int A[202020],C[202020];
const ll mo=998244353;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<404040> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	ll tot=1;
	ll eq=1;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		C[A[i]]++;
		if(C[A[i]]==1) tot=tot*2%mo;
	}
	
	vector<int> X[2];
	int step=0;
	ZERO(C);
	FOR(i,N) {
		uf(step,200000+A[i]);
		X[C[A[i]]%2].push_back(A[i]);
		C[A[i]]++;
		if(X[0].size()==X[1].size()) {
			if(X[0]!=X[1]) eq=0;
			FORR(a,X[0]) C[a]=0;
			X[0].clear();
			X[1].clear();
			step++;
		}
	}
	if(X[0].size()) eq=0;
	
	set<int> S;
	FOR(i,step) S.insert(uf[i]);
	FOR(i,S.size()) eq=eq*2%mo;
	tot=(tot+mo-eq)*(mo+1)/2%mo;
	cout<<tot<<endl;
	
	
	
}

まとめ

出だしの発想にすんなりたどり着けないな…。