题解：P7128 「RdOI R1」序列(sequence)

x_i

只能和

x_{2i}

、

x_{2i+1}

交换，看到

2i

和

2i+1

就能想到二叉树。根据

q=2^p-1

，可以看出这是一个满二叉树，而这颗树上的节点

i

的子节点分别是

2i

，

2i+1

，我们在节点

i

上标记一个数

x_i

，那么每一步操作，就是将一条树边上的两个标记数字交换。

将

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

个数字。

#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);
        }
    }
}

题解：P7128 「RdOI R1」序列(sequence)

文章操作

相关推荐

评论

题解：P7128 「RdOI R1」序列(sequence)