20221018考试总结
A
简单题，合并两个之后一定不劣，用个栈维护还没合并的东西。
B
计数题，容易发现等价于做保证全为 \(L,R\)，此时每一行的贡献独立，考虑计算每一行单独的答案，乘上其它行的方案数，得到最后的解。
计算一行的答案，考虑每一个的贡献，好像不太行，因为你需要枚举和它配对的是什么，然后就寄了，计算的时候，我们可以决定每一个选还是不选，最后取待选的个数为 \(0\) 的所有方案，同时记录方案数和答案的和，即可完成转移。
C
有趣的题。
如果采用常规的数位DP方式，那么必须记录进位数和卡界数，只能做到 \(O(nk^4)\)。
但是不妨从结果考虑，如果能计算出恰好取到 \(n\) 的方案数，并求出 \(f(n)\)，那么答案就是 \(\sum\limits_{n\ge 0} f(n)\times 取到\ n \ 的方案数\)。考虑取到 \(n\) 的方案数怎么算。
这里定义 \(\binom{a}{b}=0 \text{ when } a<0\)。
利用容斥原理，计算强制 \(k\) 个数大于 \(x\) 的方案数。 \[ ans=\sum\limits_{n\ge 0}\sum\limits_{i=0}^{k} (-1)^{i}\binom{n+k-1-i\times(x+1)}{k-1}f(n) \] 后面那个东西，\((k-1)!\) 是个常数。
提出来后是一个关于下降幂乘上 \(f(n)\)。
把下降幂展开成关于 \(n\) 的多项式，问题变成求 \[ \sum\limits_{n\ge0} f(n)n^x \] 这个可以数位DP，考虑往后面填什么，假设已经求了 \(10^i\) 以内所有答案，往后填 \(c\)，对应的变换就是求 \(\sum\limits_{0\le n<10^i} f(10n+c)(10n+c)^x\)，把 \(c\) 扔到外面，后面哪一项用二项式定理展开，就可以用原来的值推新的值了，这东西是个卷积，但是枚举 \(c\) 的部分可以扔到外面去，预处理后是 \(O(nk^2)\) 的。
但是这是有问题的，因为我们定义的组合数和下降幂算出来的组合数是不一样的，因此需要排除掉 \(n< i\times(x+1)\) 的部分，这个可以重新数位DP一次，过程是一样的。
但是有更优雅的办法，枚举每个可能的数与 \(i\times(x+1)\) 的 LCP，然后除掉当前位后面是没有限制的，后面没有限制的答案，我们已经算过了，就是前面那个值，前面的数，已经知道了，所以合并答案的过程和刚刚没有区别，由于合并答案的过程是 \(O(k^2)\) 的，所以这样会比一般的数位DP写法更加优雅。
预处理一些东西的时候要小心，注意不要超过数组或者处理少了。
D
数据结构题。
我终归还是不会区间数颜色。
区间数颜色
需要求的东西很丑，我们的数据结构，能维护的东西是满足一些偏序关系的元素的和，但是这个东西不是这样的比较优美的形式，所以考虑转化成我们的数据结构能维护的东西。
区间数颜色，就是把不好维护的，通过一个于询问无关的 \(pre\) 数组，转化成了利于维护的偏序关系。
如果考虑区间内相同数的贡献情况，它形如 \(100000\)。
这道题可能需要求一个形如 \(\text{1 -1 0 0 0 0 0}\) 的东西。
我们发现求 \(1100000\)
也是容易的，只需要记录 pre 的 pre
就可以了。于是可以加减消元得到结果。
然后树套树。
码量极其[数据删除]。
不过直接这么搞不太行，常数太大，所以可以把每个 \(\le 10^3\) 的质因子搞出来拿个块状链表维护，再转化一下，将同一质因子视为若干线段其中 \(1-3,2-4,3-5\) 这样连，可以直接得到答案，而不用做消元。
这种把颜色连成线段的思路还是有一定的启发意义。
我实在不想写这个，下面的假莫队做法好写好调还快些。
莫队
莫队思想其实是可以做强制在线题的，这基于我们能够快速从 \([l,r]\) 拓展到 \([l,r+1]\)。如果我们能够记录当前若干个状态的值，比如 \(O(n^{\frac{2}{3}})\) 个，相当于是让每个 \(O(n^{\frac{2}{3}})\) 大小的块都能记下对应的值，然后拓展的代价就是 \(O(n^\frac{2}{3})\) 的，有些题目可能会有空间问题，得就题目讨论。
这道题一个状态需要的空间大约是 \(80000\times 4 \div 1024\div1024\approx 0.3 MB\)，可以记录约 \(3000\) 个状态，这已经够用了， \(\sqrt {3000} \approx 54\)，我们能以 \(O(\frac{nq}{54})\) 的代价回答询问，对于修改，至多影响 \(3000\) 个状态，也是可以接受的。
当然，我们需要把小于 \(1000\) 的质因子提出来单独先做一遍，以免代价过大。
但是开 \(54\) 个端点不是最优的，实践表明块长小一点，比如 \(40\) ，会更加优秀，这种分块题还是需要看实际实现来调块长。
不过 \(10^5\) 的题，怎么玩都是基本不会出问题的。