题解：P7128 「RdOI R1」序列(sequence)
L0_0
·
·
题解
将 $x_i,x_j$ 交换，就可以沿着 $i\to j$ 的路径，依次交换每条边上的两个点，从而实现交换。
这样就可以让 $x_i$ 交换到 $i$，操作次数不超过 $2\log q$，重复这个操作 $q$ 次，总操作次数不超过 $2q\log q$。
路径 $i\to j$ 与比节点 $i,j$ 更深的节点无关，因而交换 $x_i$ 和 $x_j$ 不会影响到比节点 $i,j$ 更深的节点，所以要从最底层开始还原每一个数，为了更方便操作，可以从大到小遍历 $1\sim q$ 的数，这样，本题就能通过了。
时间复杂度是 $\mathcal{O}(q\log q)$，如果超时，则可能是因为没有用较快的输出方式，上述方法输出量最多可以达到 $4q\log q\le18874368$ 个数字。
```c++
#include<bits/stdc++.h>
using namespace std;
const int N = 131073;
int n, x[N], inv[N], lb[N] = {0, 0};
// x 表示原排列，inv 表示 x 的逆排列
void oper(int i, int j){
// 交换 x_i 和 x_j
swap(x[i], x[j]);
inv[x[i]] = i;
inv[x[j]] = j;
}
int lca(int x, int y){
// 计算 lca
if (x==1 || y==1) return 1;
if (x < y) swap(x, y);
while(lb[x] > lb[y]) x >>= 1;
while(x!=y){
x>>=1;
y>>=1;
}
return x;
}
int main(){
for(int i=2;i<N;i++) lb[i] = 1 + lb[i>>1]; // 预处理log2(x)
scanf("%d", &n); // 这里只不过是 q 改成 n 了
for(int i=1;i<=n;i++) scanf("%d",&x[i]), inv[x[i]] = i;
for(int q=n;q;q--){
if (x[q] == q) continue;
int r = inv[q]; // 获取 q 的位置
int lc = lca(q, r); // 其实可以不求lca，直接令lc=1
for(int a = r; a != lc; a>>=1){
printf("%d %d\n", a/2, a); // 不使用快速的输出将会TLE
oper(a/2, a);
}
vector<pair<int,int>> v;
for(int a=q; a != lc; a>>=1) v.push_back({a/2, a});
reverse(v.begin(), v.end()); // 需要反序
for(auto[i,j]:v){
printf("%d %d\n", i, j); // 不使用快速的输出将会TLE
oper(i, j);
}
}
}
```