逐步详细分析 · 清晰易懂

题面中文翻译（已提交后台）

这道题仅要求正解，要求较低，只需写出一套正确的处理流程即可。

审题分析

性质分析 · 一

拿到数列的操作方式，我们先来分析一下性质。可知其可拆分为两个行为，后面处理时分别会用到。

void op(int i){
    hst[top++]=i; // 操作记录数组
    swap(a[i],a[i+1]);
    a[i]+=k;
}

先设数列 A=(a,b,c,d,e,\ldots)，n=|A|。

对数列 A 执行一次操作 T_i，可看作为：交换 A_i,A_{i+1} 后，再将 A_i 加上 k。

依次进行操作 T_1,\ldots,T_{n-1}，分别观察前后变化。

1. 交换后：

(a,b,c,&d,e,\ldots) \\&\downarrow\\ (b,c,d,&e,\ldots,a) \end{aligned}

2. 加 k：

(b,c,d,&e,\ldots,a) \\&\downarrow\\ (b+k,c+k,d&+k,e+k,\ldots,a) \end{aligned}

我们发现，经过 n 轮操作 T_1,\ldots,T_{n-1} 后，操作后的数列相当于原数列的 n 个元素加上 k(n-1)。

故可以定义一个数列操作 T'_i，实现任意长度大于 1 的区间的增大，而区间内元素相对大小不变。

故我们可以通过抬升逆序对其中一方的区间，逐步消除逆序对。

void add(int i){
    int len=n-i+1;
    for (int j=0;j<len;j++)
        for (int k=i;k<n;k++)
            hst[top++]=k;
    for (int j=i;j<=n;j++)
        a[j]+=(len-1)*k;
}

性质分析 · 二

当 A 为一个二元组 A=(a,b)时，仅可进行操作 T_{n-1}。由前文分析，A 中中元素的相对位置仅在执行奇数次操作 T 后发生改变。

可知若 B 为逆序对，当且仅当 A_{n-1}\ge A_n+k 时，方可仅通过操作 T 使其单调不减；反之，也由此找到了唯一的无解情况。（本题数据较小，策略正确的话怎么搞都不会超过最大操作数）

解题策略

1. 针对性特判掉长度为 2 的数列

   原数列为一个二元组时进行特判，若为逆序对，当 A_{n-1} \ge A_n+k 时，宣布无解，反之进行操作 T_1。然后直接快进到输出方案。

2. 消除最后两个元素可能构成的逆序对

   二元组内处理逆序情况限制颇多。既然经过特判，此处可放心引入 A_{n-2}。通过进行操作 T'_{n-1}，即增大 A[n-1,n]，来消除可能的逆序对 (A_{n-2},A_n)。

   操作完成后我们不关心 A_{n-1} 或者其他元素的值，执行 T_{n-2} 以交换 A_{n-2},A_{n-1}，即可确保数列 A 的后两项有序。

void judge(){ // 使 (A[n-1],A[n]) 单调不减&决断 
    if (n==2){ // 特判 
        if (a[1]<a[2]+k&&a[1]>a[2])
            cout<<"No",exit(0);
        else{
            if (a[1]>a[2])
                op(1);
            return;
        }
    }
    while (a[n-2]>a[n])
        add(n-1);
    op(n-2);
}

5. 尽情消除队列中所有逆序对！

   扫描检查，发现数列中相邻两数为逆序对 (A_i,A_{i+1}) 时，通过操作 T'_{i+1}，即增大 A[i+1\ldots n]，就可以消除该逆序对，且其他数的相对位置不受影响。

void order(){ // 逐一使 A[i...n-1] 单调不减 
    for (int i=1;i<n-1;i++)
        while (a[i]>a[i+1])
            add(i+1);
}

7. 输出方案

题解实现

以下供参。

#include <iostream>
#include <algorithm>
using std::cin;using std::cout;using std::swap;
constexpr int N=1e5+1;
int n,k,a[N],hst[500000],top;
void init(){
    cin>>n>>k;
    for (int i=1;i<=n;i++)
        cin>>a[i];
}
void op(int i){
    hst[top++]=i;
    swap(a[i],a[i+1]);
    a[i]+=k;
}
void add(int i){
    int len=n-i+1;
    for (int j=0;j<len;j++)
        for (int k=i;k<n;k++)
            hst[top++]=k;
    for (int j=i;j<=n;j++)
        a[j]+=(len-1)*k;
}
void judge(){ // 使 (A[n-1],A[n]) 单调不减&决断 
    if (n==2){ // 特判 
        if (a[1]<a[2]+k&&a[1]>a[2])
            cout<<"No",exit(0);
        else{
            if (a[1]>a[2])
                op(1);
            return;
        }
    }
    while (a[n-2]>a[n])
        add(n-1);
    op(n-2);
}
void order(){ // 逐一使 A[i...n-1] 单调不减 
    for (int i=1;i<n-1;i++)
        while (a[i]>a[i+1])
            add(i+1);
}
void solve(){
    judge();
    order();
    cout<<"Yes\n"<<top<<'\n';
    for (int i=0;i<top;i++)
        cout<<hst[i]<<' ';
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    init();
    solve();
}