P8576 「DTOI-2」星之界题解

题意

给你一个序列

a

，有两种操作：

操作一：将 $[l,r]$ 内所有 $a_i=x$ 的 $a_i$ 改为 $y$ 。
操作二：求 $\prod\limits_{i = l}^{r} C_{\sum_{j = l}^{i}a_j}^{a_i}\ \bmod 998244353$ 的值。

发现求的那个式子可以转换成

\frac{(\sum\limits_{i=l}^ra_i)!}{\prod\limits_{i=l}^r(a_i!)}

。

即我们需要维护区间和、区间阶乘之积。

观察到

n\le10^5

，因此考虑分块。

每一次修改操作暴力重构散块。对于整块

k

，我们可以用并查集维护相同的数，对该块中每一个出现的数，记录第一个出现的位置，将其他相同的数的父亲指向该位置。同时维护块中每一个数的出现次数，查询时将相同的

a_i!

合并，光速幂计算。

时间复杂度

O(n\sqrt n)

，代码比较丑就不贴了。

注意并查集不要递归，否则会 MLE。

做完这道题可以去做一下未来日记，一样的套路。