前言

由 zlc 和 fhx 提供的思路，orz。

貌似是 COGS 目前的最优解？（可能是其他人的常数太大了）

思路分析

先考虑一个经典的 dp，设 $f_i$ 表示将 $1\sim i$ 划分为若干好数组的方案，则有转移 $f_i=\sum f_{j-1}$，其中满足 $[j,i]$ 是一个好区间。

这样枚举 $i$，枚举 $j$，$O(n)$ 检测，就有 $O(n^3)$ 的 dp 了。注意到 $n\le 5\times 10^5$，考虑优化。

不难发现好的子数组在原数组中，要么是奇数位置为轻元素，偶数位置为重元素；要么是偶数位置为轻元素，奇数位置为重元素，所以我们分两种情况转移：分别是以 $i$ 结尾，奇数位置为轻元素和 $i$ 结尾，偶数位置为轻元素。两者本质没有区别，我们依靠前者讨论。

我们考虑区间左端点 $j$ 可以取到哪些位置，考虑对于任意 $x\in [1,i]$，元素 $x$ 对左端点 $j$ 的约束。

1. 若 $x$ 为奇数位置，作为轻元素约束 $j$。

则 $j$ 必须满足 $[lst_x+1,n]$，即对于任意 $i\in [1,n]$，只要 $j\in [lst_x+1,n]$，区间 $[j,i]$ 就可以满足 $x$ 的限制。

证明不难，当 $j\in [lst_x+1,x]$ 时，区间至多包含一个 $x$。当 $j>x$，区间一个 $x$ 都没有，自然无法约束。

容易发现，对 $j$ 的限制个数是奇数位置所有位置。

2.若 $x$ 为偶数位置，作为重元素约束 $j$

这种情况较为复杂。

首先可以发现对 $j$ 限制个数是元素种类数，对于同一种元素，我们用这种元素在 $[1,i]$ 中最后一次出现的位置来约束 $j$。

记 $p$ 为上一个在奇数位置出现的 $x$，$q$ 为 $x$ 上一次出现的位置。当 $j\le q$ 时，$[i,j]$ 一定包含了 $q,x$，满足重元素的限制，当 $j\le p$ 时，$p$ 作为重元素出现在奇数位置，$[i,j]$ 不合法，所以 $x$ 的限制是 $j\in [q+1,p]\cup[x+1,n]$。

注意：此时是按照 $x$ 是 $[1,i]$ 最后一次出现的数，随着 $i$ 的右移，如果在偶数位置出现一个和 $x$ 一样的元素 $y$。就要先撤销 $x$ 的限制，然后加入 $y$ 的限制。

考虑如何维护满足限制的端点：维护每个位置满足限制的个数，不难维护出限制的总个数，对于一个位置，如果它足一个限制，就让他的标记数组加一。如果一个位置满足的限制个数为总个数，就说明 $[j,i]$ 是一个合法的端点。

注意一种特殊情况是 $[i,i]$ 是合法区间，我们只统计 $j\in [1,i-1]$ 的合法左端点。

直接用数组模拟是 $O(n^2)$，容易用线段树优化到 $O(n\log n)$，具体的记录每个区间任意位置满足限制个数最大值，满足限制个数达到这个最大值的 $f_{i-1}$ 之和，pushup 分讨一下即可。

然后这个问题就解决了。

先创建一个 $map$，使 $m[队列元素]=$队列编号，这样后面好查找元素的组别；

再创建一个队列 $q[301]$，$q[i]$ 表示队列编号为 $i$ 的排队情况。$q[0]$ 表示小组的排序；

队列输入不用多说，只需要注意一个新小组的人入队要给新小组排上队；

队列输出时查看 $q[0]$ 队头，看到小组编号后查该小组的队头，再输出，注意小组的人全部出队后要把空小组删掉。

【题解】

        算法一：

       思路：动态规划，$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$；

Subtask1: n,m≤100

注意到我们可以枚举每一对 (E,S) 并判断 Bob 是否必胜，最后将必胜的方案数除以 nm 就是答案。

判断是否必胜我们直接将边 E 删去并从起点 S 开始搜索即可，时间复杂度 O(n2m)。期望得分 30pts。

Subtask2: w=1

除非 S 是叶子且 E 恰好是 S 的唯一出边，Bob 都是必胜的。统计是简单的，不再赘述。

Subtask3: n,m≤5000

考虑从边双连通分量入手，我们枚举 E。

若 E 不是割边，那么删除 E 不会影响 S 所能到达的点/边集。只要原图中还存在边权与 E 相等的边，那 Bob 就是必胜的，贡献为 n。

若 E 是割边，那么删除 E 会将边双树分为两个连通块，而 S 只能遍历其所处的连通块，所以 Bob 必胜等价于该连通块中有边权与 E 相等的边。直接遍历两个连通块来判断即可。

割边的数量可以达到与 n 同阶，故时间复杂度为 O(nm)。期望得分 60pts。

Subtask3: n,m≤106

考虑优化 E 是割边时的判断过程。注意到一个连通块必定是边双树中的一颗子树或者全树扣掉一颗子树，而后者可以直接用全局减去该子树得到。于是问题等价于求一棵子树中边权与根的父边相等的边的数量。

这个问题的做法非常多，容易 O(n) 实现，期望得分 100pts。