巅峰手速 题解

· · 题解

简要题意

给你一个长为 n 的序列，每次可以取出第 k 个元素放在序列开头或者末尾（k 为常数）。请给出一种排序方案或者判断无解，输出方案时可以将相邻的相同操作绑在一起视作一次操作。

算法一

我会暴力搜索！

期望得分：10。

算法二

考虑 k=2 的情况。

首先把序列元素变为 1 到 n 的排列。

我们从 n 到 3 枚举元素 i，先用不超过两次操作把 i 移动到 1 号位，再把 i+1 移动到 3 号位。然后把 i 移动到 2 号位。最后再用一次操作把 3 到 n 的元素移动到正确位置，看 1 和 2 需不需要再交换。

这样做操作次数不超过 4n。

期望得分：16。

算法三

很多时候这种判断是否有解的排序题你找一个跟逆序对有关的必要条件就得到了正确的结论，于是考虑猜结论。

在这之前，首先要特判 k=1 或者 k=n 的情况。

如果序列有相同元素，你可以钦定相同元素的大小，这样初始状态的逆序对数既可以是奇数也可以是偶数。如果序列没有相同元素，当 k 为偶数时你把元素放在序列开头会改变逆序对数的奇偶性，当 n-k 为奇数时你把元素放在序列末尾会改变逆序对数的奇偶性，而排序后逆序对数为 0，是偶数。如果无论如何逆序对数的奇偶性都只能是奇数那就一定无解。所以无解的充分条件是序列没有相同元素且逆序对数为奇数且 k 为奇数且 n-k 为偶数。

你提交代码，发现这个结论是对的。至于条件的充分性可以通过后面的构造证明。

期望得分：20。

算法四

这里给出一种操作次数不超过 6n 的构造方案。

还是先把序列元素变为 1 到 n 的排列。

然后用算法二的方法先把 1 到 k-2 的元素移动到正确位置，再把 k+1 到 n 的元素移动到正确位置，这时如果运气好 k-1 和 k 在正确位置就完事了。否则如果 n-k 为奇数，可以找到这样一种操作序列来交换 k-1 与 k 的位置。

r 1
l 1
r 1
l k-1
r 1
l 1
r 1
l k-1
……
l k-1
r 1

如果 n-k 为偶数并且 k 是偶数则可以先把 k+2 到 n 的元素移动到正确位置，再把 1 到 k-1 的元素移动到正确位置，再用同样的方法交换 k 和 k+1。

如果 n-k 为偶数并且 k 是奇数，因为初始状态下逆序对数是偶数且操作过程不会改变逆序对数的奇偶性，所以最后两个元素位置一定是对的，不需要特殊处理。

直接暴力维护序列是 O(n^2) 的，但是可以用平衡树优化到 O(n\log n)。

期望得分：30\sim60。

算法五

有一个比平衡树更优美的维护序列的方法。

我们分开维护 1 到 k 和 k 到 n 的序列，并在序列上维护第 k 个位置的指针。每次操作会移动一边的指针，并把另外一边指针指向的数字改为移动后指针指向的数字。这样做的好处是每次操作只有常数个元素的位置改变了，可以直接用数组存下每个元素的位置。具体实现中，我们可以钦定最后需要把指向第 k 个位置的指针移到初始位置，移动元素 i 时就直接把他移动到序列的第 i 个位置，最后再判断是否需要交换 k-1 和 k。

虽然这样做并不能优化操作次数，但是能帮助我们更好的理解问题。

期望得分：60。

算法六

我们可以对算法五做两个优化。

  1. 因为我们限定指向第 k 个位置的指针最后要回到初始位置，也就是限定他在左右两边的序列上都转整数圈。转一整圈时逆序对数奇偶性不会改变。如果一开始逆序对数是偶数一定不需要交换 i-1 和 i。如果一开始逆序对数是奇数就先操作一次把他变成偶数，这样操作次数不会超过 4n。

  2. 每次把 i 移动到正确位置时都会把原本在第 i 个位置的元素移动到序列的另外一边，如果被移出来的元素也和 i 在同一批次的移动中，这时我们立即把他移动到正确的位置，就减少了 2 次可能的移动。所以在把元素移动到正确位置时，先移动已经在序列另一端的元素。剩下的还没排序的元素形成了若干个置换环，对每个环随便选一个元素先移动。这样操作次数不会超过 5n。

两个优化加在一起再调整一下常数，操作次数就不会超过 3n。

因为要算逆序对数，时间复杂度是 O(\sum n\log n)。

期望得分：100。

std:

#include <bits/stdc++.h>
#define LL long long
#define mes(s, x) memset(s, x, sizeof(s))
#define lb(i) (i & -(i))
#define Maxn 200005
using namespace std;
inline LL read(){char c;c = getchar();while(!(('0' <= c && c <= '9') || c == '-')) c = getchar();bool flag = 0;if(c == '-'){flag = 1;c = getchar();}LL tot = 0;while('0' <= c && c <= '9'){tot = 10 * tot + c - '0';c = getchar();}return flag ? -tot : tot;}
int a0[Maxn], a[Maxn], re[Maxn], b[Maxn], lst[Maxn], n, k;
int s[Maxn];
void add(int i){
    while(i <= n){
        s[i]++;
        i += lb(i);
    }
}
int sum(int i){
    int t = 0;
    while(i){
        t += s[i];
        i -= lb(i);
    }
    return t;
}
int l[Maxn], r[Maxn], p[Maxn], lp, rp;
void swp(){
    if(l[lp]) p[l[lp]] = rp;
    else p[r[rp]] = -lp;
    swap(l[lp], r[rp]);
}
char nt;
int nx;
void f(char t, int i){
    int x;
    if(t == 'l'){
        x = (lp - i + k) % k;
        if(l[lp] == 0) swp();
        lp = i;
    }else{
        x = (i - rp + (n - k + 1)) % (n - k + 1);
        if(r[rp] == 0) swp();
        rp = i;
    }
    if(x && nt != t){
        if(nx) printf("%c %d\n", nt, nx);
        nt = t, nx = 0;
    }
    nx += x;
    if(nt == 'l') nx %= k;
    else nx %= n - k + 1;
}
void solvel(int i){
    if(p[i] <= 0){
        f('l', -p[i]);
        f('r', rp == k ? k + 1 : k);
    }
    int x;
    while(i <= k - 2){
        x = l[i];
        f('l', i);
        f('r', p[i]);
        i = x;
    }
}
void solver(int i){
    if(p[i] >= 0){
        f('r', p[i]);
        f('l', lp == k ? k - 1 : k);
    }
    int x;
    while(i >= k + 1){
        x = r[i];
        f('r', i);
        f('l', -p[i]);
        i = x;
    }
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    int T = read(), m, x;
    LL tot;
    while(T--){
        n = read(), k = read();
        for(int i = 1; i <= n; i++) re[i] = a0[i] = read();
        if(k == 1 || k == n){
            x = 0;
            if(a0[n] > a0[1]) x = 1;
            for(int i = 2; i <= n; i++){
                if(a0[i - 1] > a0[i]){
                    if(x) x = -1;
                    else x = i;
                }
            }
            if(x == 0) x = 1;
            if(x == -1) printf("No\n");
            else{
                printf("Yes\n");
                if(k == 1){
                    if(x != 1) printf("r %d\n", x - 1);
                }else{
                    if(x != 1) printf("l %d\n", n - x + 1);
                }
                printf("o\n");
            }
            continue;
        }
        sort(re + 1, re + n + 1);
        m = unique(re + 1, re + n + 1) - re - 1;
        for(int i = 1; i <= m; i++) b[i] = 0;
        for(int i = 1; i <= n; i++) b[a0[i] = lower_bound(re + 1, re + m + 1, a0[i]) - re]++;
        for(int i = 1; i <= m; i++) b[i] += b[i - 1];
        for(int i = n; i >= 1; i--) a[i] = b[a0[i]]--;
        for(int i = 1; i <= n; i++) s[i] = 0;
        tot = 0;
        for(int i = n; i >= 1; i--){
            tot += sum(a[i]);
            add(a[i]);
        }
        nx = 0;
        if(tot % 2){
            if(m != n){
                for(int i = 1; i <= m; i++) lst[i] = 0;
                for(int i = 1; i <= n; i++){
                    if(lst[a0[i]]){
                        swap(a[i], a[lst[a0[i]]]);
                        break;
                    }
                    lst[a0[i]] = i;
                }
            }else if(k % 2 == 0){
                nt = 'l', nx = 1;
                a[0] = a[k];
                for(int i = k; i >= 1; i--) a[i] = a[i - 1];
            }else if(n % 2 == 0){
                nt = 'r', nx = 1;
                a[n + 1] = a[k];
                for(int i = k; i <= n; i++) a[i] = a[i + 1];
            }else{
                printf("No\n");
                continue;
            }
        }
        printf("Yes\n");
        for(int i = 1; i < k; i++) p[l[i] = a[i]] = -i;
        l[k] = 0;
        for(int i = k; i <= n; i++) p[r[i] = a[i]] = i;
        lp = rp = k;
        if(r[k] <= k - 2){
            for(int j = k + 1; j <= n; j++){
                if(r[j] > k - 2){
                    f('r', j);
                    solvel(r[k]);
                    break;
                }
            }
        }
        for(int i = n; i >= k; i--) if(r[i] <= k - 2 && !(i == rp && r[i] == lp)) solvel(r[i]);
        for(int i = k; i >= 1; i--) if(l[i] && l[i] <= k - 2 && l[i] != i) solvel(l[i]);
        if(l[k - 1] >= k + 1){
            f('l', k);
            solver(l[k - 1]);
            if(l[k] >= k + 1 && lp != k) solver(l[k]);
        }else{
            f('l', k - 1);
            if(l[k] >= k + 1) solver(l[k]);
        }
        for(int i = k; i <= n; i++) if(r[i] >= k + 1 && r[i] != i) solver(r[i]);
        f('r', k);
        f('l', k);
        if(nx) printf("%c %d\n", nt, nx);
        printf("o\n");
    }
    return 0;
}