kmjp's blog

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

第三回 アルゴリズム実技検定 : N - 入れ替えと並び替え

これは割とあっさり。
https://atcoder.jp/contests/past202005-open/tasks/past202005_n

問題

整数列Aがあり、最初A[i]=iである。
以下のクエリを順次終えた後のAを答えよ。

  • 整数xが指定されるので、A[x]とA[x+1]をスワップする
  • 区間[L,R]が指定されるので、A[L]....A[R]を昇順に並べ替える。

Aはだいたい昇順であることがわかる。
よって、A[i]>A[i+1]になっている可能性があるindex iの集合Cを持とう。

後者のクエリでは、Cのうち[L,R]の範囲内の添え字だけ愚直に処理すればよい。

int N,Q;
int A[202020];
set<int> cand;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	for(i=1;i<=N;i++) A[i]=i;
	while(Q--) {
		cin>>i>>x>>y;
		if(i==1) {
			swap(A[x],A[x+1]);
			cand.insert(x+1);
			cand.insert(x);
			cand.insert(x+2);
		}
		else {
			while(1) {
				auto it=cand.lower_bound(x+1);
				if(it==cand.end() || *it>y) break;
				int cur=*it;
				cand.erase(*it);
				if(A[cur]<A[cur-1]) {
					swap(A[cur],A[cur-1]);
					cur--;
					if(cur>1 && A[cur]<A[cur-1]) cand.insert(cur);
					cand.insert(cur+2);
				}
			}
			cand.insert(x);
			cand.insert(y+1);
		}
	}
	FOR(i,N) cout<<A[i+1]<<" ";
	cout<<endl;
}

まとめ

ここまではすんなり。