CF1987G1 Spinning Round (Easy Version) 题解

---

题意回顾

给定一个排列 $p_1,\dots,p_n$，对于每个下标 $i$ 定义：

• $l_i$：$i$ 左边第一个大于 $p_i$ 的位置（不存在则为 $i$）
• $r_i$：$i$ 右边第一个大于 $p_i$ 的位置（不存在则为 $i$）

每个点 $i$ 必须选择连一条有向边 $i\to l_i$ 或 $i\to r_i$。我们想要在连通图的前提下最大化图的直径。简单版本中所有 $s_i$ 都是 ?，即每个点都可以自由选择方向。

$n \le 4\cdot 10^5$

---

核心观察

1. 边的方向性

考虑将有向边视为 $i\to l_i$ 或 $i\to r_i$，则边总是从值较小的顶点指向值较大的顶点，即 $a\to b$ 意味着 $p_a<p_b$。

由于每个顶点恰好有一条出边，直径在无向意义下形如：

$$v_1 \to v_2 \to v_3 \to \dots \to v_k \leftarrow \dots \leftarrow v_{d-1} \leftarrow v_d $$

中间不可能出现 $\leftarrow v_i \to$ 的情况（因为这样 $v_i$ 就有两条出边了）。因此直径可以拆成两个单向链：

• 左链：$v_1 \to v_2 \to \dots \to v_k$
• 右链：$v_d \to v_{d-1} \to \dots \to v_k$

2. 割裂数组

论断：存在一个下标 $m$，使得左链（去掉汇合点）完全落在 $[1,m]$ 中，右链（去掉汇合点）完全落在 $[m+1,n]$ 中（或反过来）。

也就是说，我们可以把排列切成左右两半，让两条链分别位于自己的一侧，而不跨越切割线。

该性质的证明见文末 Proof 1。

---

算法设计：Meet in the Middle

利用上述割裂性质，我们可以：

1. 从左向右扫描，用单调栈维护以每个元素为终点（即该元素是链中 $p$ 值最大的那个）的最长路径长度。
2. 从右向左做同样的扫描。
3. 枚举切割线 $m$，将左右两侧的最优路径合并。

单调栈扫描

设当前扫描到位置 $x$，维护一个栈，栈内元素为 $(位置,\;长度)$，其中 $p$ 值单调递减。

插入 $x$ 时：

• 弹出所有 $p$ 值比 $p_x$ 小的元素，同时用弹出的长度更新当前答案。
• 将 $(x, \max\_popped + 1)$ 压入栈中。

同时维护一个数组 best[i]：只使用前 $i$ 个元素时能获得的最大路径长度。

示例（$p=[4,1,5,3,2,6]$）：

$$\begin{aligned} i=1 &: s=[(4,1)], & best[1]=1 \\ i=2 &: s=[(4,2),(1,1)], & best[2]=2 \\ i=3 &: s=[(5,3)], & best[3]=3 \\ i=4 &: s=[(5,3),(3,1)], & best[4]=3 \\ i=5 &: s=[(5,3),(3,2),(2,1)], & best[5]=4 \\ i=6 &: s=[(6,4)], & best[6]=4 \end{aligned} $$

best[i] 可以在 $O(n)$ 或 $O(n\log n)$ 内求出。

合并答案

不能简单地把左右两边的最大 best 拼接起来。考虑 $p=[2,1\mid 3,4]$，左侧栈为 $[2,1]$，右侧为 $[4,3]$，但 $2$ 和 $4$ 不能直接相连，因为 $3$ 挡住了。

设左侧前缀最大值依次为 $a_1,a_2,\dots,a_s$，右侧后缀最大值依次为 $b_1,b_2,\dots,b_t$。

• 若切割线落在 $a_i \le m < a_{i+1}$，则合并的是左侧 $a_i$ 和右侧 $a_{i+1}$（右侧以 $a_{i+1}$ 为根的路径）。
• 同理，若切割线落在 $b_i \le m < b_{i+1}$，则合并的是左侧 $b_i$ 和右侧 $b_{i+1}$。

实际上，用 $a_i$（前缀最大值中的第 $i$ 个）与其对应的 best 就足够完成合并。

总复杂度 $O(n\log n)$ 或 $O(n)$，取决于 best 的计算方式。

---

AC 代码

#include <bits/stdc++.h>
using namespace std;

#define ii pair<int,int>
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define sz(x) (int)(x).size()

int n;
int arr[400005];
string s;

int ans[2][400005];   // 正/反向 best 数组
int t[400005];
vector<int> stk[2];    // 正/反向单调栈中的位置

// 扫描 [l,r]，计算 val[x] = 以 x 为右端点时的最大路径长度，
// 返回最后的单调栈 (位置, 长度)
vector<ii> process(int l, int r, int val[]) {
    vector<ii> v;
    int curr = 0;

    rep(x, l, r + 1) {
        ii res = {x, 0};
        while (!v.empty() && arr[v.back().fi] < arr[x]) {
            int t = v.back().se; v.pob();
            if (!v.empty()) v.back().se = max(v.back().se, t + 1);
            res.se = max(res.se, t + 1);
        }
        v.pub(res);

        curr = max(curr, res.se + sz(v));
        val[x] = curr;
    }
    return v;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin.exceptions(ios::badbit | ios::failbit);

    int TC;
    cin >> TC;
    while (TC--) {
        cin >> n;
        rep(x, 1, n + 1) cin >> arr[x];
        cin >> s;   // 简单版本中 s 全为 '?'

        // 正向和反向各扫一次
        rep(z, 0, 2) {
            auto v = process(1, n, ans[z]);
            stk[z].clear();
            for (auto [a, b] : v) stk[z].pub(a);
            reverse(arr + 1, arr + n + 1);
        }

        // ans[0][stk[0][0]] 是正向全局最大值的位置，对应反向位置 n - stk[0][0] + 1
        int mx = ans[0][stk[0][0]] + ans[1][n - stk[0][0] + 1] - 1;

        // 枚举单调栈中相邻元素作为分割点
        rep(z, 0, 2) {
            rep(x, 0, sz(stk[z]) - 1) {
                process(stk[z][x], stk[z][x + 1], t);
                rep(y, stk[z][x], stk[z][x + 1])
                    mx = max(mx, t[y] + ans[z ^ 1][n - y]);
            }
            reverse(arr + 1, arr + n + 1);
        }

        cout << mx - 1 << endl;   // 边数 = 点数 - 1
    }
}