この回は散々な出来でした。
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"); } }
まとめ
まぁまだここは簡単。