CF1987G2 Spinning Round (Hard Version) 题解

---

题意回顾

给定排列 $p_1,\dots,p_n$ 与字符串 $s$（$s_i\in\{\text{L},\text{R},?\}$）。对每个 $i$：

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

每个 $i$ 按 $s_i$ 的指示连边：

• $\text{L}$：必须连 $(i,l_i)$
• $\text{R}$：必须连 $(i,r_i)$
• $?$：可自由选择 $(i,l_i)$ 或 $(i,r_i)$

求所有可构造连通图的最大直径，若不连通输出 $-1$。

---

连通图约束

图有 $n$ 个点 $n$ 条边，若连通则为基环树。只有全局最大值可以有自环（$l_{max}=r_{max}=max$），其他前缀最大值若选 $\text{L}$ 或后缀最大值若选 $\text{R}$ 就会形成自环，导致不连通。

因此：

• 全局最大值左边链（沿 $l$ 走到底）上的点不能选 $\text{L}$
• 全局最大值右边链（沿 $r$ 走到底）上的点不能选 $\text{R}$

据此检查可行性，并将这些链上的 $?$ 强制改为合法方向。此后连通性自动满足，可任意决策。

---

笛卡尔树结构

对 $p$ 建大根笛卡尔树：每个节点 $u$ 有左儿子 $ls_u$、右儿子 $rs_u$，$p_u$ 是子树最大值。

在新图中：

• 向左跳：沿笛卡尔树一直向上跳到某个祖先，且第一次以右儿子身份向上跳
• 向右跳：沿笛卡尔树一直向上跳到某个祖先，且第一次以左儿子身份向上跳

因此一条新图路径实质是笛卡尔树上一条链的子集。

---

状态设计

枚举 $u$ 作为路径的 LCA。

• 若两端点 $x,y$ 分别在 $u$ 的左右子树，则直接拼接左右子树的最优路径。
• 若 $x,y$ 在 $u$ 的同一子树内，只需记录三种状态即可覆盖所有情况。

定义 $f_{u,0/1/2}$：

状态	含义
$f_{u,0}$	子树内向左跳出子树的最长路径长度
$f_{u,1}$	子树内向右跳出子树的最长路径长度
$f_{u,2}$	子树内两条分别向左、向右的不交路径的最大长度和

为方便转移，将"跳出子树的那一步"也算入状态值。

---

转移方程

设 $lc=ls_u$，$rc=rs_u$。

$f_{u,0}$（向左跳路径）

$$f_{u,0} = \max\begin{cases} f_{lc,0} \\ \text{若 }c_u\neq\text{R}:\ \max\big(\max(f_{rc,0},\,f_{lc,1}),\,0\big)+1 \end{cases} $$

$f_{u,1}$（向右跳路径）

$$f_{u,1} = \max\begin{cases} f_{rc,1} \\ \text{若 }c_u\neq\text{L}:\ \max\big(\max(f_{lc,1},\,f_{rc,0}),\,0\big)+1 \end{cases} $$

$f_{u,2}$（两条不交路径）

基础拼接（一左一右）：

$$f_{u,2} = f_{lc,0}+f_{rc,1}$$

若 $c_u\neq\text{R}$（可以向左跳），额外考虑：

$$f_{u,2} = \max\begin{cases} f_{rc,1}+1 \\ f_{rc,2}+1 \\ f_{rc,1}+f_{lc,1}+1 \end{cases} $$

若 $c_u\neq\text{L}$（可以向右跳），额外考虑：

$$f_{u,2} = \max\begin{cases} f_{lc,0}+1 \\ f_{lc,2}+1 \\ f_{lc,0}+f_{rc,0}+1 \end{cases} $$

---

答案统计

在 DFS 过程中实时更新答案 $ans$：

$$\begin{aligned} ans &= \max(ans,\ \max(0,f_{lc,1})+\max(0,f_{rc,0})) \\[4pt] \text{若 }c_u\neq\text{R}&:\ ans = \max\begin{cases} f_{lc,0}+\max(0,f_{rc,0})+1 \\ f_{u,2}+1 \end{cases} \\[4pt] \text{若 }c_u\neq\text{L}&:\ ans = \max\begin{cases} \max(0,f_{lc,1})+f_{rc,1}+1 \\ f_{u,2}+1 \end{cases} \end{aligned} $$

注意在根节点处不额外统计 $f_{u,2}+1$（因为根没有父亲，不存在向上跳的那一步）。

---

复杂度

• 建笛卡尔树：$O(n)$
• 树形 DP：$O(n)$
• 总复杂度：$O(n)$

---

AC 代码

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

const int N = 4e5 + 5, inf = 1e9;
int T, n, p[N], stk[N], st, ls[N], rs[N];
int ans, f[N][3], rot;
char c[N];

inline void MAX(int &a, int b) {a = (a >= b ? a : b);}

inline void dfs(int u){
    f[u][0] = f[u][1] = f[u][2] = -inf;
    if(!u) return ;
    int lc = ls[u], rc = rs[u];
    dfs(lc), dfs(rc);
    
    // f[u][0]：向左跳路径
    MAX(f[u][0], f[lc][0]), MAX(f[u][1], f[rc][1]);
    if(c[u] != 'R') MAX(f[u][0], max(max(f[rc][0], f[lc][1]), 0) + 1);
    if(c[u] != 'L') MAX(f[u][1], max(max(f[lc][1], f[rc][0]), 0) + 1);

    // f[u][2]：两条不交路径
    MAX(f[u][2], f[lc][0] + f[rc][1]);
    if(c[u] != 'R') MAX(f[u][2], f[rc][1] + 1), 
                    MAX(f[u][2], f[rc][2] + 1), 
                    MAX(f[u][2], f[rc][1] + f[lc][1] + 1);
    if(c[u] != 'L') MAX(f[u][2], f[lc][0] + 1), 
                    MAX(f[u][2], f[lc][2] + 1), 
                    MAX(f[u][2], f[lc][0] + f[rc][0] + 1);

    // 统计答案
    MAX(ans, max(0, f[lc][1]) + max(0, f[rc][0]));
    if(u == rot) return ;
    if(c[u] != 'R') MAX(ans, f[lc][0] + max(0, f[rc][0]) + 1), 
                    MAX(ans, f[u][2] + 1);
    if(c[u] != 'L') MAX(ans, max(0, f[lc][1]) + f[rc][1] + 1), 
                    MAX(ans, f[u][2] + 1);
}

inline void solve(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &p[i]);
    scanf("%s", c + 1);
    
    // 建大根笛卡尔树
    ans = st = 0, stk[1] = 0;
    for(int i = 1; i <= n; ++i){
        ls[i] = rs[i] = 0;
        while(st && p[stk[st]] < p[i]) --st;
        if(st) rs[stk[st]] = i;
        ls[i] = stk[st + 1];
        stk[++st] = i, stk[st + 1] = 0;
    } 
    rot = stk[1];
    
    // 检查连通性并修改 s
    for(int i = ls[rot]; i; i = ls[i]){
        if(c[i] == 'L') {puts("-1"); return ;}
        if(c[i] == '?') c[i] = 'R';
    }
    for(int i = rs[rot]; i; i = rs[i]){
        if(c[i] == 'R') {puts("-1"); return ;}
        if(c[i] == '?') c[i] = 'L';
    }
    
    dfs(rot);
    printf("%d\n", ans);
}

signed main(){
    cin >> T;
    while(T--) solve();
    return 0;
}