これは割とあっさり。
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; }
まとめ
ここまではすんなり。