观察到所有互不相同的歌曲对答案的贡献独立，于是我们逐歌曲类型考虑。
假设当前类型出现位置为 $a_1,a_2,\dots,a_k$。我们计算有多少个 $P_1,P_2,S_1,S_2$ 使得 $(P_1,S_1)$ 包含至少一个 $a$，和有多少个使得 $(P_2,S_2)$ 包含至少一个 $a$。

---

对于 $(P_1,S_1)$：

定义 $c(X,Y)$ 为对所有左端点在 $\{-X+1,-X+2,\dots,0\}$，右端点在 $\{0,1,\dots,Y-1\}$ 的区间的子区间数量和。则：

$$c(X,Y)=\sum_{i=1}^X\sum_{j=1}^Y\binom{i+j}{2}=\sum_{i=1}^X\sum_{j=1}^Yij+\binom i2+\binom j2 $$$$=(\sum_{i=1}^Xi)(\sum_{j=1}^Yj)+Y(\sum_{i=1}^X\binom{i}{2})+X(\sum_{j=1}^Y\binom{j}{2}) $$

将这些和预处理即可。

枚举 $P_1$ 里的第一个 $a_i$，固定为 $a_i$，则有 $c(a_i-a_i-1,n-a_i+1)$ 个 $(P_1,P_2)$ 满足 $P_1$ 包含 $a_i$。
最后，如果这个歌曲编号是 $x$，将累计起来的贡献乘 $c(x,n-x+1)$ 即可得到总共 $(P_1,S_1,P_2,S_2)$ 方案数。

---

对于 $(P_2,S_2)$：

现在我们根本不可能用 $c(X,Y)$ 了，因为可行的 $(P_1,P_2)$ 数量依赖于位置。
定义 $d(X,i)$ 为 $(P_1,P_2)$ 数量，使得 $P_2$ 包含 $i$ 并且 $P_2$ 左端点大于等于 $X$。第一发现 $P_1$ 和 $P_2$ 右端点不受任何限制也和左端点独立，枚举 $i$ 到 $P_1$ 右端点之间的可能左端点数量得到 $(P_1,P_2)$ 可行右端点数量为

$$\sum_{r=1}^{n-i+1}r$$

通项即可。我们再枚举 $P_2$ 左端点的位置，$P_1$ 必须在 $P_2$ 左端点左边，于是左端点数量为

$$\sum_{r=X}^ir$$

通项即可。按照第一部分一样方法处理。

---

所有类型贡献加起来得到答案，时间复杂度 $O(n)$。