ARC187 Add and Swap Editorial

题意

长为 n 的正整数序列 a，操作 m 次：

• 每次操作选择一个 i(1 \le i < n)，并交换 a_i 和 a_{i+1}，然后使 a_i \gets a_i + K。

思路

以下的递增都指非严格单调递增，即 \forall 1\le i < j \le n，a_i \le a_j。

容易发现的一点是相邻的两项 \color{black}a_i,a_{i+1} 可以通过两次操作变成 \color{black} a_i+K,a_{i+1}+K。我们先挑战让 a_1,a_2,\dots,a_{n-1} 变成递增序列，容易有个简单的思路就是按 i=2,3,\dots,n-1 的顺序，用上面的方法反复使 a_i \gets a_i + K, a_{i+1} \gets a_{i+1}+K 直到 a_{i-1} \le a_i。

接下来序列只剩下 a_{n-1} 和 a_n 的关系不确定了。

1. 当 a_{n-1} \le a_n 时，整个序列就递增了。

2. 当 a_{n-1} > a_n 时，若只选择 n-1 进行操作，发现有可能 a_n > a_{n-1}+K，交换无数次都无法递增，就陷入僵局了。借鉴前面的思路，选择 n-2 进行操作直到 a_n \le a_{n-1}+K，然后选择 n-1 操作一次，于是 a_{n-1} \le a_n 了。

最后，再反复操作直到整个序列递增即可。

Tips：事实上，上述讨论不包含所有情况，分析一下会发现 n=2 时并不能选择 n-2 来操作，因此有以下三种情况：

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
using namespace std;
const int N = 5e5+5, M = 3e4+5, mod = 1e9+7;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
int n, K;
LL a[N];
vector<int> res;
#define pb(x) push_back(x)
int main() {
    FASTIO;
    cin >> n >> K;
    rep(i, 1, n) cin >> a[i];
    if (n == 2) {
        if (a[1] <= a[2]) {
            cout << "Yes\n";
            cout << "0";
            return 0;
        }
        else if (a[2]+K > a[1]) return cout << "No\n", 0;
        else {
            cout << "Yes\n";
            cout << "1\n1";
            return 0;
        }
    }
    rep(i, 2, n-1) {
        while (a[i] < a[i-1]) {
            a[i] += K, a[i+1] += K;
            res.pb(i), res.pb(i);
        }
    }
    if (a[n] < a[n-1]) {
        while (a[n-1] < a[n]+K) {
            a[n-1]+=K, a[n-2]+=K;
            res.pb(n-2), res.pb(n-2);
        }
        res.pb(n-1);
        swap(a[n-1], a[n]);
        a[n-1]+=K;
        while (a[n-1] < a[n-2]) {
            res.pb(n-1), res.pb(n-1);
            a[n-1] += K, a[n] += K;
        }
    }
    cout << "Yes\n" << res.size() << '\n';
    for (auto it : res) cout << it << ' ';
    return 0;
}