题解：P15576 [USACO26FEB] Good Cyclic Shifts G

梨花诗 · 2026-03-04 12:55:45 · 题解

感觉题挺牛的。

如果一个排列能够通过至多 f(p) 次相邻元素交换变为 p_i=i 首先这个条件等价于 f(p) \ge inv(p) 也就是逆序对个数。

首先让我们观察一下 f(p)=\sum_{i=1}^N \frac{|p_i-i|}{2} 式子的性质，考虑把绝对值去掉。

那么和怎么和逆序对扯上关系呢？我们考虑对于任何一个满足 p_i > i 的元素，整个数组中小于 p_i 的数共有 p_i - 1 个。

在位置 i 的左边，最多只有 i - 1 个位置。哪怕 i 左边的位置全被小于 p_i 的数占满，也还剩下至少 (p_i - 1) - (i - 1) = p_i - i 个小于 p_i 的数，它们必然存在于位置 i 的右边。那么就必然产生 p_i - i 个逆序对。

我们把所有 p_i > i 的元素贡献的“保底”逆序对加起来：

所以只有取等时才是好的排列哦。

这意味着，对于每一个元素，不能产生任何“多余”的逆序对，这就是一个比较经典的问题了。

假设排列中存在 321 模式，即存在下标 i < j < k，满足 p_i > p_j > p_k。我们盯着中间这个元素 p_j 来看：

它无非就两种情况：

1. 情况一：p_j \leq j 它对 f(p) 的贡献是 0。但 j < k 且 p_j > p_k，它和后面的 p_k 形成了一个逆序对。这个逆序对在 f(p) 里没有被算进去，此时必然 inv(p) > f(p)。

2. 情况二：p_j > j 此时i < j，且 p_i > p_j。这说明左边混进了一个比它大的数。这就导致右边必然会多出一个比它小的数，从而又产生了一个“额外”的逆序对。必然 inv(p) > f(p)。

那么剩下的问题就简单了，破环成链然后统计下 i < j < k，满足 p_i > p_j > p_k 即可。具体来说先用单调栈维护出每个位置 j 左边第一个比他大的位置 i 和右边第一个比他小的位置 k，然后我们对这样的 i, j, k 记录每个 k 位置左边最大的与他组成的 i ，也就是维护 k 离他最近的一个 i 记作 mx[k]，这样判断一个区间是否合法只需要判断区间中最大的 mx[k] 是否大于等于左端点即可。也有线性的差分做法。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )
#define repf(i, a, b) for(int i = (a); i >= (b); i -- )
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int P = 1e9 + 7;
int a[N << 1]; int lmx[N << 1], rmi[N << 1];
int stk[N<<1], top; int c[N << 1]; int b[N << 1];
int f[18][N << 1], lg[N << 1];
inline int Q(int l, int r)
{
    int len = r - l + 1;
    return max(f[lg[len]][l], f[lg[len]][r - (1 << lg[len]) + 1] );
}
int main()
{
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while(T -- )
    {
        int n; cin >> n;
        rep(i, 1, n) cin >> a[i], a[i + n] = a[i];
        int nn = n << 1;
        rep(i, 1, nn) b[i] = 0;
        stk[0] = -1;
        top = 0;
        rep(i, 1, nn)
        {
            while(top && a[stk[top]] < a[i]) top --;
            lmx[i] = stk[top];
            stk[++ top] = i;
        }
        top = 0;
        repf(i, nn, 1)
        {
            while(top && a[stk[top]] > a[i]) top --;
            rmi[i] = stk[top];
            stk[++ top] = i;
        }
        rep(i, 1, nn) if(lmx[i] != -1 && rmi[i] != -1)
        {
            b[rmi[i]] = max(b[rmi[i]], lmx[i]);
            c[lmx[i]] ++, c[rmi[i] + 1] --;
        }
        rep(i, 2, nn) lg[i] = lg[i >> 1] + 1;
        rep(i, 1, nn) f[0][i] = b[i];
        rep(j, 1, 17) rep(i, 1, nn - (1 << j) + 1) f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
        int sm = 0;
        rep(i, 1, n) sm += c[i];
        vector<int> v;
        rep(i, n + 2, nn + 1)
        {
            if(Q(i - n, i - 1) >= i - n);
            else v.push_back(nn - i + 1);
            sm += c[i - n], sm += c[i];
        }
        cout << v.size() << '\n';
        reverse(v.begin(), v.end());
        for(auto x : v) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}