题解

Difficulty：3.9 / Easy

Tag：倍增

注意到求出排列会在什么时候重复是困难的。所以考虑其他做法。

考虑倍增。定义 $\text{jump}[i][j]$ 为经过 $2^j$ 次转换后的排列。显然可以倍增。

然后二进制枚举 $m$ 通过 $\text{jump}$ 数组即可求出具体位置。做完了。

namespace cjdst{
    const int N = 100, M = 30;
	int jump[N + 5][M + 5];

	void solve(){
		int n, m;
		std::cin >> n >> m;
		int l1, r1, l2, r2;
		std::cin >> l1 >> r1 >> l2 >> r2;
		std::vector <int> ans(n + 5);
		for(int i = 1; i <= n; i++){
			ans[i] = i;
		}
		std::reverse(ans.begin() + l1, ans.begin() + r1 + 1);
		std::reverse(ans.begin() + l2, ans.begin() + r2 + 1);
		for(int i = 1; i <= n; i++){
			jump[i][0] = ans[i];
		}
		for(int i = 1; i <= 30; i++){
			for(int j = 1; j <= n; j++){
				jump[j][i] = jump[jump[j][i - 1]][i - 1];
			}
		}
		for(int i = 1; i <= n; i++){
			int cur = i;
			for(int j = 0; j <= 30; j++){
				if(m >> j & 1) cur = jump[cur][j];
			}
			std::cout << cur << '\n';
		}
	}
}

时间复杂度：$O(n\log m)$。