kmjp's blog

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

AIM Tech Round 4 : A. Sorting by Subsequences

この回は散々な出来でした。
http://codeforces.com/contest/843/problem/A

問題

N個のdistinctな整数からなる数列Aが与えられる。
この数列を(不連続でもよいので)複数の部分列に分割し、個々の部分列の要素間を昇順にソートすることを考える。
ソート後、数列全体が昇順にソートされた状態にしたい。

最大で何個の部分列に分割してもその状態にできるか。

解法

Aの要素を座標圧縮で0~(N-1)に整理しよう。
A[i]=jの場合、i番目とj番目は同じ部分列に含めなければならない。
よってUnion-Findでそれらをまとめ上げていこう。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

int N;
int A[101010];
vector<int> B;
vector<int> R[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], B.push_back(A[i]);
	sort(ALL(B));
	FOR(i,N) {
		A[i]=lower_bound(ALL(B),A[i])-B.begin();
		uf(A[i],i);
	}
	
	FOR(i,N) R[uf[i]].push_back(i+1);
	int ret=0;
	FOR(i,N) if(R[i].size()) ret++;
	_P("%d\n",ret);
	FOR(i,N) if(R[i].size()) {
		_P("%d",R[i].size());
		sort(ALL(R[i]));
		FORR(e,R[i]) _P(" %d",e);
		_P("\n");
	}
}

まとめ

まぁまだここは簡単。