【题解】

        算法一：

       思路：动态规划，$dp[i]$ 是前 $i$ 个元素的有效划分方案数，则 $f[0]=1$（空数组有 $1$ 种划分方式），$f[i]$ 为所有满足 $[j+1,i]$ 是好数组的 $f[j]$ 的和。

       时间复杂度：$O(n^2)$，即 $5000*5000=2.5*10^7$，期望 $15$ 分。

       瓶颈：不能快速判断数组是否是好数组，不能快速累加 $f[j]$;

        算法二：

       思路：有几处优化；

           $1$.对每个元素 $a[i]$，计算 $pre[i]$（上一次出现位置）和 $nxt[i]$（下一次出现位置），所以可以由好数组的性质“对于子数组内的重元素 $a[i]$，其前后出现位置必须在子数组外（否则会影响交替性）”优化判断好数组的条件；

           $2$.若 $j$ 在 $[L..R]$ 内时 $[j+1..i]$ 是好数组，则 $f[i]$ 需要累加 $f[L]+f[L+1]+...+f[R]$，所以用双线段树。好数组有两种起始类型（轻元素开始或重元素开始），需分别维护。因此使用两个线段树 $seg[0]$ 和 $seg[1]$，分别对应两种起始类型，每个线段树节点存储“区间内最大有效长度”和“对应方案数总和”支持区间增减（通过延迟标记）和单点更新；

            $3$.预先生成“区间更新事件”：当遍历到位置 $i$ 时，哪些 $j$ 的范围会因 $a[i]$ 的加入而成为有效划分点，事件按生效位置排序，遍历数组时依次触发，动态更新线段树，确保查询到的 $f[j]$ 都是有效的。

           同样方式计算 $f[i]$，最终需减去重复计算的 $f[i-1]$，对 $1000003$ 取余后输出。

       时间复杂度：$O(n*logn)$，即 $5*10^5*log5*10^5≈10^7$,轻松过 $4$ 秒时限；

       期望得分：$100$；