自动搬运

查看原文

来自洛谷，原作者为

	chroneZ **

搬运于2025-08-24 22:47:03，当前版本为作者最后更新于2023-11-07 21:29:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

神仙构造题。

依次考虑每个数 $i \in [1, n]$，尝试将值 $i$ 操作到位置 $i$ 上。由于单次操作是对奇偶项分组后合并为一个新的序列，故通过操作可以将一个位置到目标位置的距离减半。这样就可以产生一个 $\Theta(n \log n)$ 的做法了：

// f[a[i]] = i
for(int i = 1; i <= n; i++) {
    while(a[i] != i) {
    	// i 需放置在子区间的偶数位上
        if((f[i] - i) & 1) {
            apply(i, f[i]);
        } else {
            apply(i + 1, f[i]);
        }
    }
}

但是这种做法不够优秀，对本题而言需要近乎线性的解法。

延续这个思路并没有什么优秀做法，这个时候可以尝试一下转换视角。正难则反，如果这个问题是让我们通过逆操作，将排列 1 2 3 4 5... 操作成给定序列，是否有新的性质呢？

这也引出了本题最人类智慧的一步：运用转置原理，对逆排列通过逆操作进行排序，最后倒序输出操作序列。其中逆操作形如：选择一个子区间，将前半部分与后半部分取出，两部分交替加入结果序列。

这样一来，只要进行一步 $(1, 2i)$ 的操作，就可以令 $i$ 的位置倍增到 $2i$ 处。当 $2i > n$ 时，操作 $(2i - n + 1, n)$ 可将 $i$ 的位置移动到 $n$ 上。

这样做好在哪里呢，这时 $\text{highbit}$ 越大，代价反而越小了。形式化的讲，此时需要操作 $\lfloor \log n \rfloor - \lfloor \log i \rfloor + 1$ 次（这里就认为 $n$ 是 $2$ 的幂次了）。对这个式子求和，如果你要忽略下取整符号，可以用斯特林公式 $n! \approx \sqrt{2 \pi n} (\frac ne) ^ n$ 推导出一个粗略上界是 $(1 + \log_2 e) n$。当然也可以直接进行整数推导，可以证明操作次数上界在 $2n$ 附近。最终结论就是，这样做的操作量是 $\Theta(n)$ 的。

于是，考虑通过逆操作对原排列的逆排列排序，从 $n$ 到 $1$ 依次使每个数归位即可。结合一些随机扰动，可以进一步将操作次数卡进 $6000$。

个人认为这里逆操作的动机并不显然，但对这类构造题而言反向考虑的确是一个常见的套路，解构造题还是要善于转换视角。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr int N = 3000 + 10;
int n, a[N], b[N], f[N];

inline void maintain() {
	for(int i = 1; i <= n; i++) {
		f[a[i]] = i;
	}
}
vector<pair<int, int>> seq;
inline void apply(int l, int r) {
	seq.emplace_back(l, r);
	int t = l; 
	for(int i = l + 1; i <= r; i += 2) {
		b[t++] = a[i];
	}
	for(int i = l; i <= r; i += 2) {
		b[t++] = a[i];
	}
	for(int i = l; i <= r; i++) {
		a[i] = b[i];
	}
	maintain();
}
inline void applyInv(int l, int r) {
	seq.emplace_back(l, r);
	int mid = (l + r - 1) >> 1, t = 0;
	for(int i = l, j = mid + 1; t < r - l + 1; t++) {
		if(t & 1) {
			b[t] = a[i++];
		} else {
			b[t] = a[j++];
		}
	}
	for(int i = l; i <= r; i++) {
		a[i] = b[i - l];
	}
	maintain();
}
inline void work(int l, int r) {
	while((l << 1) < r) {
		applyInv(1, l << 1);
		l <<= 1;
	}
	applyInv(2 * l - r + 1, r);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rec[N];

int main() {
	// freopen("sort.in", "r", stdin);
	// freopen("sort.out", "w", stdout);
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	maintain();
	for(int i = 1; i <= n; i++) {
		swap(f[i], a[i]);
		rec[i] = a[i];
	}
	maintain();

	do {
		seq.clear();
		for(int i = 1; i <= n; i++) {
			a[i] = rec[i];
		}
		maintain();
		
		int T = 10;
		while(T--) {
			int l = rng() % n + 1, r = rng() % n + 1;
			if(l > r) {
				swap(l, r);
			}
			if(l == r) {
				continue;
			}
			applyInv(l, r); 
		}
		for(int i = n; i >= 1; i--) {
			if(f[i] == i) {
				continue;
			}
			work(f[i], i);
		}
	} while(seq.size() >= 6000);

	reverse(seq.begin(), seq.end());
	cout << seq.size() << "\n";
	for(auto [l, r] : seq) {
		cout << l << " " << r << "\n";
	}
}