A. matrix

当然考虑左端点为 $l$的所有矩形的贡献。

通过一个 trie，对 trie 上每个节点开一个 set，来找到每个串 $s$ 存在的位置。

那么可以把当前答案的形式化成 $ans=\sum \limits_{s} val_s$ ，其中 $val_s$ 表示这个串出现的区间数。

$val_s$ 直接通过简单的在 set 上查前驱后继即可维护。然后在 trie 上每个节点另外开一个变量 $sum$ 表示子树和。

直接访问 $sum_{root}$ 累计答案即可。

考虑左端点每次的 $+1$ 操作，实际上把根节点的每个儿子合并到一起，并作为新的根节点即可。

然后需要写一个 trie 的合并函数，与线段树合并类似可分析函数调用次数是正确的。

对于 set 中元素的处理，可以直接启发式合并，然后就没了，这样做的复杂度是 $O(nmlog^2)$ 的。

然后有一个结论，就是说使用 splay ，然后直接把小的 splay 按照中序遍历插入大 splay。

这样的复杂度可以去一个 $log$，原因大概是 splay 的 finger search 性质。

B. sequence

容易发现，如果固定一个右端点。

因为 $and$ 操作的性质，不同的区间取值只有 $log$ 种。

考虑维护出区间取值的变化位置。

对于每个区间的取值，判断是否被 $k$ 整除。

如果整除，那么直接进行区间加 $1$ 操作。

右端点从左往右扫，同时进行区间加法操作。

离线询问，在对应的右端点处区间查询即可。

然后大概学到了如何用树状数组维护区间修改、区间查询。

思想是将修改转化为差分，询问即做两次前缀和。

写出来式子发现可以交换求和符号，于是可以用两个树状数组维护。

C. permutation

发现同时有 $a,b$ 两个要求，不是很好维护。

其实很多排列的题都有的套路是，每次考虑最大的元素 $n$ 或者最小的元素 $1$。

考虑每次选择一个位置放置 $n$ ，那么显然会对 $a,b$ 均造成 $1$ 的贡献。

然后 $a,b$ 都不会跨越这个 $n$，于是可以对左右分别 dp 处理。

然后发现这个 dp 的转移和第一类斯特林数一毛一样。

于是 $ans=\sum \limits_{i=1}^n s(i-1,a-1)s(n-i,b-1)\binom{n-1}{a-1}$。

然后发现只要求 $a-1,b-1$ 列的斯特林数。

求一列斯特林数的方法是用 EGF，$i$ 个点能构成的环排列个数就是 $(i-1)!$，然后整个快速幂就完事了。

然而这题的数据范围 $2e5$ ，显然多项式 $ln,exp$ 必死。

考虑上面那个式子，发现 $ans=s(n-1,a-1+b-1)\binom{a-1+b-1}{a-1}$ ，原因可以直接从组合含义理解。

然后现在只需要求单点斯特林数，用较小的常数求一行斯特林数就行了。