ABC405G

记一道非常具有教育意义的题目。题目大意是给你一个大小为 $N$ 的数组和 $Q$ 次询问，询问的结构是 $L,R,X$ ，需要求出 $[L, R]$ 中小于 $X$ 的数任意排列能组成多少种不同的序列。

首先很容易想到的是维护$x$出现的次数，记为 $c_x$ 。所求答案就是 $\frac{(\sum\limits_{i=1}^{X-1}c_i)!}{\prod\limits_{i=1}^{X-1}c_i!}$ 。不考虑 $X$ ，想一想该怎么维护这个答案，对于每个区间直接维护 $c$ 是很困难的，否则会在计算答案的时候因为 $X$ 太大爆炸。同时发现加入一个数是可以直接 $O(1)$ 维护贡献的，所以想到直接维护乘积，记为 $prod$ 和 $c$ 数组，查询可以用莫队做。

现在考虑 $X$ 的限制，查询答案的时候对应 $X$ 直接用权值树状数组查询数量和乘积逆元就行，但是这样还是有一个问题，多了个 $\log$ 会 T。

这个问题和一般的莫队的区别在于多了一个 $X$，导致需要动态修改/查询。现在就是要把这个动态修改/查询的部分优化到 $O(1)$ 。把修改和查询分开来考虑，修改做了$N\sqrt Q$次，查询做了 $Q$ 次。修改部分需要 $O(1)$，查询的限制放宽到根号级别。因为是单点修改，想到用分块来做。

具体思路是：

• 修改：更新 $prod$ 和 $c$ 数组
• 查询：累计 $prod$ 和 $c$ 数组，分块查询

具体实现的过程中产生了许多卡常问题。首先是直接用逆元做除法的时候会产生一个 $\log$，导致 T 了好多次。正确做法是预处理阶乘的逆元。同时莫队的实现中需要采用奇偶块优化卡卡常，因为之前没有被卡过所有一直没有学这个技巧，实际上很简单：朴素做法存在每个块都要让 $r$ 指针回到最小的位置的缺陷，实际上 $r$ 的顺序不关键，只要能保证线性移动就行。这个时候考虑到上一个块的 $r$ 指针会在比较后面的位置，倒着排序这个块的 $r$ 就可以从后往前扫卡卡常，下一个块再从前往后交替做就行。