AtCoder Beginner Contest 247

E

考虑枚举右端点 $R$，计算对于每个 $R$ 有多少个左端点 $L$ 满足条件。

左端点需要满足的条件如下：

• $[L, R]$ 中需要有 $x$ 和 $y$ 至少各一个。
• $[L, R]$ 中不能出现比 $x$ 大或比 $y$ 小的元素。

转化条件：

• 设 $px$ 表示 $[1, R]$ 中最右边 $x$ 的位置，$py$ 表示 $[1, R]$ 中最右边 $y$ 的位置，$L \leqslant \min(px, py)$。
• 设 $gex$ 表示 $[1, R]$ 中最右边大于 $x$ 的位置，$ley$ 表示 $[1, R]$ 中最右边小于 $y$ 的位置，$L > \max(gex, ley)$。

于是只需要在枚举 $R$ 的同时维护 $px, py, gex, ley$ 并将 $\min(px, py) - \max(gex, ley)$ 计入答案即可。

时间复杂度 $\Theta(n)$。

F

考虑到每个数都需要存在，并且它在恰好两个位置中出现过（这两个位置可能相同），于是将这两个位置在一张图中连无向边。

观察到每个点度数都恰好为 $2$，于是连边后构成若干个环。

易知，整体方案数为每个环方案数的乘积，每个环的方案数为点覆盖方案数。

考虑求解大小为 $m$ 的环的点覆盖方案数。考虑强行将环从 $n \sim 1$ 处拆成链，设 $f_{i, 0/1}$ 表示仅考虑 $1 \sim i$ 的链，中间每条边都至少有一个端点被选，第 $i$ 个点被选或不选的方案数。转移是简单的。但是我们发现最后计算答案时需要知道第一个点到底选没选，于是需要钦点第一个点选或不选分别转移。

将转移方程写出来后，我们观察到它其实是两个斐波那契状物之和，于是用数列 $f_1 = 1, f_2 = 3, f_i = f_{i - 1} + f_{i - 2}$ 来拟合是可行的（当然也可以直接算，复杂度不变，代码也没长多少）。

综上即可算出原问题答案，时间复杂度 $\Theta(n)$。

Code Link