CF1109E
很生气，写个唐诗题写了好久。
感觉是看错题导致的。
题面略。
考虑这个直接做不太可做。因为不保证有逆元。
但是它保证整除，考虑对模数分解成：
\[mod = \prod_{i = 1}^{cnt} p_i^{c_i} \]这种形式，那么我们如果可以整除可以直接维护对于 \(p_i\) 的 \(c_i\) 不是吗？
所以我们考虑对数质因数分解，维护 \(10\) 个质因数的指数，余下的数可以用 exgcd 求逆元。
然后就做完了，代码很抽象，不知道为什么可以写到 3k。
CF1109F
很经典的 LCT 数生成树，吗？
考虑维护左端点 \(l\) 的最大可以扩张到的右端点 \(r\)，使得不存在环，不难使用 LCT 维护连通性问题。
那么就是数 \([l, r]\) 内有多少个区间 \([l, i]\) 满足区间的点在四连通性的情况下数一棵树。
考虑对于树这种特殊形态使用森林经典结论 \(V - E = 1\)。
那么我们就可以计算在左端点为 \(l\) 的情况下，每个点连了多少条边，注意到这个是对一个后缀的区间产生贡献。
那么我们可以使用线段树维护区间加来维护 \(V - E\)，怎么数 $ = 1$ 呢？
根据 CF526F 的想法，借助最小值维护，发现 \(V - E = 1\) 的时候是左式最小值，可以维护最小值个数。
然后就做完了。
标签：可以,CF1109F,CF1109E,最小值,端点,维护 From： https://www.cnblogs.com/Custlo/p/17989650