9.19

abc371F：两种做法。等差数列线段树和 ODT。两种做法实现难度相同，不过后者似乎要快很多。

花 1 个小时复习了 ODT 怎么打，他复杂度正确的原因是因为每次 query(l, r) 过后马上进行了 assign。然后就是基础的 split 和 getpos 操作，记得给边界插入 set。

线段树也是维护三元组 【l, r, pos】 表示左右 id。如果有区间操作的话 lzy 就是 pos 表示等差数列的第一项。每次下传标记记得去右儿子的时候把 lzy 加 lenLS，然后一个线段树节点就是由多个等差数列构成。

注意不要写动态开点的线段树，非常容易 TLE。

abc317G：这玩意场上想了一半正解。

考虑到正式考试不可能高精度，所以我们使用正常算法。

这个东西本质上是多个同余方程合并，每次在合法解里面贪心选，显然 lcm 作为模数需要高精度。

注意到如果：\((m_1,m_2)=1\)，则必然可以满足。所以我们要对所有 \(m\) 之间的 gcd 来考虑是否满足，eg：\(\mod 2 = 1,\mod 4 = 0\) 显然无解。

又能够想到质数拆分，如果对于所有质数来判断一定是等价的。而质数因数个数显然是亚根号级别。

所以我们顺序遍历每个环，记录环长 \(l\)，然后枚举换上第一个应该是本来的第 \(i\) 个，容易发现这样子要转 \(x=l-i\) 次。那么我们就判断可行即可。

对 \(l\) 的所有质因子考虑（这里考虑所有 \(m_i^{a_i}\) 形式），容易发现等价转化后 \(x\mod m_i^{a_i}\) 这个值在所有环上都一样，所以对每个因数记录一个 mod 值即可。

最后贪心选每个环第一个位置最小的即可。复杂度线性根号，远远跑不满。