Luogu4692 [Ynoi2016] 谁的梦

题意：定义一个序列的权值为不同数字的个数。

给出 个序列 ，在每个序列中选择一个连续非空子串，拼接起来。

求所有选法得到的序列的权值总和。如果一个序列能通过多种方法被选择出来，要计算多次。

需要支持单点修改。答案对 取模。

允许离线，，时限 。

---

简单题。

将所有作为值的数字离散化。

不考虑修改

记不同的数的总数为 ，分别考虑每个数的贡献。

正难则反，对于每个数 ，计数其没有出现的所有选法。

总选法是 ，记 。

对于序列 ，记 表示在 中选一个不包含 的区间的方案数。

则答案为：

然而 可能都很大，不能处理到每个 。

注意到当 中有数 时， 才会 。这类特殊位置的个数是 的。

记 。初始时令 。

逐个考虑 出现过的序列的贡献，将 除去 后，乘上特殊计算的 。

考虑修改

我们单点修改序列 后，会影响两个 的计算。

我们需要支持：插入，删除，计算不包含关键位置的数的个数。

注意到答案与极长不含关键点连续段有关，用 std::set 维护即可。

为了方便，可以将 个序列拼在一起，这样每个颜色就只需要开一个 set 了。

对于那些不等于 的 ，用 std::map 维护。

注意可能有某个 ，此时不便于做除法，要特殊记零因子的个数。

复杂度 。