apio到NOI
.到NOI前的模拟赛，博客就写道这里了。The Last Month。Ragnarök。
7,19 Link
卷爷的模拟赛。我愿意成为APIO复刻活动。
很难受，如果APIO的时候好好听课好好总结今天的题就应该会了。
T1
让你维护两个pair集合，动态维护（插入删除） \(\min{(\max(a_1+a_2,b_1+b_2))},(a_1,b_1)\in S_1,(a_2,b_2)\in S_2\)。
删除很难，容易使用时间分治。但是这样似乎处理不掉 \(\log^2\) 的复杂度。
具体的我们如果只有加的操作可以，按照一维为下标，然后二分，移一下项发现就是 \(premin(x)-x>b-a\) 这种东西，也很容易直接线段树二分。
key point 时间上二分（分治）受阻的话，那就想想序列分治，有时能达到不劣，甚至更优的做法。（Apio T2）。
我们不可能时间分治，因为不是很可能 \(O(1)\) 干掉只加的问题。
考察我们刚才得到的，\(premin(x),x\) 事实上如果我们取到等号，那么就是另一对，这就启示要根据 \(b-a\) 分类讨论。
剩下的我们按 \(b-a\) 排序，这样贡献由左→右产生，容易想到类似cdq分治结构吗，直接维护分治树即可，复杂度\(q\log q\)。
T2
如果仔细听听cxr怎么推的FwT的话，，，，就好了，实际上Fwt那个占位多项式。。。得更
需要学习。
真正的7,19 Link
今天是Ragnarök Project 的第一天，怎么说也不能不写博客。
模拟赛真的好绝望，看着大家随便切T1，我还对着我5min就得到的哈希无能狂怒。。。
具体的你发现割边需要，当且仅当存在两条边，\(e_1\in T_1,e_2\in T_2\)。他们分割成的点集相同。实际上是分治结构。
然后我去想哈希。容易 \(n^2\log n\) 做，然后没有出路了。（我真的意识到这个做不出来，但是，，，很难跳出思维定势。）
我实际上也认为这个哈希很容易将一些结构破坏掉，导致不好做。。但是一直没往合成一棵树上想。
实际上他们把两棵树放到了一棵树上考虑。对于每一条正常树边，你考虑他能对应出哪个红色边。
就是覆盖了的边。。。。。。
这样容易\(\log^2\) 去树剖了。甚至这一步可以哈希。
P2看”我知道王子“大佬写的，似乎倒着做，就能把”找到分割点集的边“并分割，换成”找到同时链接两个点集的边“并合并这两个点集。
这样似乎启发式维护mulitset就好了。正难则反这个我初三WC时候就知道的东西千万不能忘呀！！
先写题解，再写代码。。
这种题目。。。。反正可以发现这肯定就是一个DP套DP，当然这类题我没咋做过，模拟赛出了一次又一次还是不会。真是太菜了。
如果真要硬想LCS自动机这种的话，不要忘记了差分这个关键trick。但是这样无法避免实际上LCS自动机的庞大。
对于状态的压缩只能自求多福了。。。。
但是如果你把这个东西当成DP套DP(Dfa上DP) 的话，你应该现象如何判定答案（类似麻将先想”判胡自动机“一样）。
由于我们的误差只有 \(2\) ，可以搞一些和LCS不一样的DP。
\(f_{i,j,k}\) 表示两序列填到了 \(i\) 第一个删了 \(j\) 个，第二个删了 \(k\) 个能否匹配（不补齐）。
这样的DP是 trivial 的。只不过你需要大量分讨。在分讨的过程中，发现状态需要能找到最后一个字符位置，所以还需要记录是否删了最后一个。
有点过于复杂，等会再写。。。。。状态数会爆炸。wait for upd
T3只能感慨智商低下 \[ F(x)=\prod_{0\le i^2< x} (x-i^2) \] 问 \(x\in [l,r]\) 满足 \(F(x)\bmod m=0\) 的 \(x\) 的个数。
首先这东西吓死人 \(F\) 一点性质你都推不出来。
小结论 \(F(x)\bmod m=0\Longrightarrow F(x+m)\bmod m=0\) ，这说明了对于 \(m\) 同余的，一定后缀全都是。
那你还能干啥？l,r除了差分一下还能干啥。。这时一定要尝试考虑 \(m\) 如果存在性质的话，结果是什么样子的。
- \(m\) 是质数。对于 \(\bmod m=x\) 的那很显然第一个必须是 \(p\mid x-i^2\) 这个很容易找到（通过枚举有限的 \(i^2\bmod m\) 找到 \(x\) 最小）。
- \(m=p^k\) 。类似的我们还是要找 \(p\mid x-i^2\) （否则必然是没用的），\(i^2\bmod m\) 有限并且 \(i>kp\) 的时候如果还没解的话，那就寄了不可能有解了。\(p\) 个一循环，只多不少。这样枚举 \(i\leq kp\) 同时枚举 \(x-i^2=cp\) 正好 \(k\cdot M\) 枚举量。
这时回去看看我们要找的是最小的 \(F(x)\bmod m=0\) 的呀，如果两个互素的 \(m_1,m_2\) ，只需要 \(F(x)\bmod m_1=0,F(x)\bmod m_2=0\) 就好，这样就是一个类似crt的过程，很简单，复杂度就是 \(O(M\log n)?\) 的。