「Giraffes」长颈鹿排列题解

问题分析

我们需要重新排列长颈鹿，使得对于任意区间 $[l, r]$，都不满足：

1. 存在 $k \in (l, r)$ 使得 $P_l < P_k > P_r$（存在比两端都高的）
2. 存在 $k \in (l, r)$ 使得 $P_l > P_k < P_r$（存在比两端都矮的）

换句话说，排列必须避免在任意区间内同时出现"山峰"和"山谷"。

核心思路

这个问题可以通过动态规划优化来解决，关键观察是：满足条件的排列实际上是单峰序列或其变种。

关键性质

满足条件的排列具有以下特征之一：

• 完全递增或递减
• 先递增后递减（单峰）
• 某些特殊的双调排列

算法详解

1. 状态定义

代码中使用了复杂的状态转移和树状数组优化：

int f[maxn][4], g[maxn][4];  // DP状态数组

f[i][j] 表示以位置 $i$ 结尾的某种合法子序列的相关信息，其中 $j=0,1,2,3$ 可能表示不同的模式。

2. 树状数组优化

代码使用了两个树状数组类进行优化：

namespace t1 {
    // 标准树状数组，支持前缀最小值查询
    inline int query(int x) {
        int R = inf;
        for (; x; x ^= lowbit(x)) chkmin(R, t[x]);
        return R;
    }
}

namespace t2 {
    // 反向树状数组，支持后缀最小值查询  
    inline int query(int x) {
        int R = inf;
        for (; x <= (n << 1); x += lowbit(x)) chkmin(R, t[x]);
        return R;
    }
}

3. 多方向状态转移

代码通过8种不同的查询模式来更新状态：

void add(int l, int r, int d) {
    const int u = d + r - l;
    qu[0][r].push_back(mkp(n - l + d, -d));
    qu[1][u].push_back(mkp(n - l + d, -l));
    // ... 7种其他模式
}

这些模式对应不同的转移方向：

• 从左到右的递增序列
• 从右到左的递减序列
• 单峰序列的左右部分
• 等等

4. 迭代求解

算法通过迭代方式逐步扩展合法序列的长度：

for (;;) {
    // 清空和初始化
    F(i,0,7) F(j,1,n) qu[i][j].clear();
    F(i,1,n) F(j,0,3) g[i][j] = inf;
    
    // 添加各种转移
    F(i,1,n) if (f[i][0] <= min(n-i, n-a[i]))
        add(i, i + f[i][0], a[i]);
    // ... 其他方向的转移
    
    // 使用树状数组处理查询
    t1::init(), t2::init();
    F(i,1,n) {
        chkmin(g[i][2], t1::query(a[i]-i+n) + a[i]);
        for (auto [x,y] : qu[0][i]) t1::add(x, y);
    }
    // ... 处理其他7种模式
    
    // 更新状态并检查终止条件
    F(i,1,n) F(j,0,3) f[i][j] = g[i][j];
    
    if (!flag) break;
    ++ans;
}

算法正确性

为什么这样能找到最长合法序列？

1. 状态设计：f[i][j] 跟踪了以位置 $i$ 结尾的合法子序列的信息
2. 多模式覆盖：通过4种状态和8种查询模式，覆盖了所有可能的合法序列模式
3. 逐步扩展：每次迭代尝试扩展序列长度，直到无法继续扩展
4. 答案计算：最终答案为 $n - \text{最长合法序列长度}$

时间复杂度

• 每次迭代：$O(n \log n)$
• 总迭代次数：最长合法序列长度，最坏 $O(n)$
• 总复杂度：$O(n^2 \log n)$，对于 $n \leq 8000$ 可接受

样例验证

样例1：6\n5 4 6 1 3 2

• 最长合法序列长度为4
• 需要移动 $6-4=2$ 只长颈鹿

样例2：4\n4 1 3 2

• 原排列已合法，最长序列长度为4
• 需要移动 $4-4=0$ 只

样例3：7\n3 1 6 7 4 2 5

• 最长合法序列长度为5
• 需要移动 $7-5=2$ 只

总结

本题的巧妙之处在于：

1. 问题转化：将排列约束转化为寻找最长合法子序列
2. 状态设计：使用多维状态表示不同的序列模式
3. 数据结构优化：使用树状数组加速状态转移
4. 多方向处理：通过8种查询模式覆盖所有转移方向

这种"DP + 数据结构优化 + 多模式处理"的方法在解决复杂序列问题时非常有效，特别是当问题具有单调性相关性质时。