AtCoder ABC #253 (NOMURA プログラミングコンテスト2022) : G - Swap Many Times

GまではいいけどExでダメだった。
https://atcoder.jp/contests/abc253/tasks/abc253_g

問題

整数N,L,Rが与えられる。
1≦i＜j≦Nとなる整数のペア(i,j)を辞書順に並べた列を考える。n個目のペアを(X[n],Y[n])と表記する。

数列Aの初期値は、[1,2,3,...,N]であるとする。
ここで、AのX[L]番目とY[L]番目の要素をswapし、X[L+1]番目とY[L+1]番目の要素をswapし、…X[R]番目とY[R]番目の要素をswapした場合、Aがどうなるかを答えよ。

解法

X[L]=X[i]であるようなiと、X[i]=X[R]であるようなiについては、愚直にスワップしよう。
X[L]＜X[n]＜X[R]であるnについて考える。
これは(X[n],X[n]+1),(X[n],X[n]+2),....,(X[n],N)の順でswapすることになるが、これは結局末尾の要素をX[n]番目の位置に持ってくることに相当する。

よって、末尾の(X[R]-X[L]-1)要素をX[L]に逆順で持ってくれば、X[L]＜X[n]＜X[R]であるnに対するswapをまとめて完了できる。

ll N,L,R;

int num[202020];
int A[502020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,20> bit;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>R;
	
	int AL,AR,BL,BR;
	
	FOR(i,N) {
		num[i]=N-1-i;
		if(L) {
			if(L<=num[i]) {
				AL=i,AR=i+L;
				L=0;
			}
			else {
				L-=num[i];
			}
		}
		if(R) {
			if(R<=num[i]) {
				BL=i,BR=i+R;
				R=0;
			}
			else {
				R-=num[i];
			}
		}
	}
	FOR(i,N) A[i]=i+1;
	
	
	if(AL==BL) {
		for(x=AR;x<=BR;x++) {
			swap(A[AL],A[x]);
		}
	}
	else {
		for(x=AR;x<N;x++) {
			swap(A[AL],A[x]);
		}
		int step=BL-AL-1;
		if(step) {
			rotate(A+AL+1,A+N-step,A+N);
			reverse(A+AL+1,A+AL+step+1);
		}
		for(x=BL+1;x<=BR;x++) {
			swap(A[BL],A[x]);
		}
	}
	FOR(i,N) cout<<A[i]<<" ";
	cout<<endl;
}

まとめ

細かいミスはあったけど、割とすんなり。