AtCoder AGC #001 : F - Wide Swap

コードはシンプルなんだよな。
http://agc001.contest.atcoder.jp/tasks/agc001_f

問題

1～NのPermutation Pが与えられる。
このPの２要素P[i],P[j]に対し、|i-j|≧Kかつ|P[i]-P[j]|=1であれば要素を交換できる。

上記交換を繰り返して得られる辞書順最小の数列を求めよ。

解法

Pを逆にしたというか90度回転した数列Qを考える。
すなわちQ[i]はiがP中何要素目にあるかを示しており、Q[P[i]]=iとする。

Pの辞書順最小値を求める事は、Qの辞書順最小値を求めるのと同義である。
問題文にある交換処理をQで考えると、隣接要素の差がK以上なら交換可能ということになる。
逆に、Q中でQ[i]の手前に差がK未満の値がいくつかあるなら、Q[i]はそれらの数より手前に持ってくることはできない。

Q中で1から順にどこまで数字を手前に持ってこれるかを決めていこう。
今P中の数値xをできるだけ手前に持ってくることを考える。
すなわちQ[x]=iとなっているところを、できるだけ小さくしたい。

その場合、Q[1..(i-1)]中に位置未確定のx+K未満の値があるかどうかを見ていこう。
(xより手前にあり、かつxより小さい値は先に位置を確定しているのでx未満の値は無視してよい)
これは区間の最小値を求めるSegTreeを用いて得ることができる。

Q中手前に位置未確定のx+K未満の値があった場合、再帰的にそちらを先に処理する。
x+K未満の値が１個もない場合、xは位置未確定の要素のうち最も手前に来る。
この処理を繰り返して、求める数列を手前から順に決めていける。
位置確定済みの項目が上記区間の最小値で再度検出されないよう、決めた要素はSegTree上で値を大きくしておくとよい。

最後にまたQを90度回転すると解。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<25;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> seg;

int N,K;
int P[501010];
int R[501010];
int vis[505050];
int fix;

void go(int i) {
	while(1) {
		int a = seg.getval(0,P[i]);
		if(a>=i+K) break;
		go(a);
	}
	
	vis[i]=1;
	R[i] = ++fix;
	seg.update(P[i],1<<30);
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
		seg.update(P[i],i);
	}
	
	FOR(i,N) if(vis[i]==0) go(i);
	FOR(i,N) cout<<R[i]<<endl;
}

まとめ

これは思いつかんなぁ。