题解

思路

在序列首尾加入值只出现一次的哨兵 $A_0=0,A_{N+1}=N+1$，并要求选择两个哨兵。

做法

设相邻选中的位置为 $i<j$，唯一性等价于开区间 $(i,j)$ 内既没有 $A_i$，也没有 $A_j$；否则可以把相应端点换到区间内部得到另一种取法，反之从左右两端贪心匹配会得到同一组下标。记 $next_i$ 为 $A_i$ 下一次出现的位置，$prev_j$ 为 $A_j$ 上一次出现的位置，则合法转移恰为 $j\le next_i$ 且 $prev_j\le i$。

令 $dp_j$ 为以 $j$ 作为当前最后位置的合法路径数，则 $dp_j$ 是所有 $i\in[prev_j,j-1]$ 且 $next_i\ge j$ 的 $dp_i$ 之和。按 $j$ 从左到右扫描，在树状数组的下标 $i$ 处维护尚未过期的 $dp_i$，到 $next_i+1$ 时删除，再查询区间 $[prev_j,j-1]$ 即可。$dp_{N+1}$ 包含空子序列，最后减一。

复杂度

时间复杂度 $O(N\log N)$，空间复杂度 $O(N)$。