侵删。
chz
T1
给一个序列和\(k\)，定义一个区间的权值是其中只出现一次的数的个数，求有多少种划分这个序列的方式，使得每一段的权值不超过\(k\)。\(n,k\leq 10^5\)。
爆力dp显然，如何优化?
考虑加入一个数的时候，用数据结构维护左端点，那么相当于对一个区间的权值\(+1\)，另一个区间\(-1\)，要查询全局权值\(\leq k\)的位置的和。容易用分块搞定，每一块开一个桶就好了。
T2
dsq
T1
给一个序列，支持单点修改，查询一个区间所有子序列和的\(\mathrm{mex}\)，或者说做01背包之后最小的不能表示出的数。\(n\leq 5\times 10^5,q\leq 10^5,a_i\leq 10^9\)。
很有意思。考虑静态全局询问怎么做?
我们把所有数从小到大排序，维护一个极长的可以表示出的前缀\([0,r]\)。假设现在要加入\(x\)，如果\(x\leq r+1\)，我们用\(r+x\)更新\(r\)；否则，答案就是\(r\)了。
如何加速?发现这个看起来很像能翻倍的样子，容易发现如果我们每次把所有\(\leq r+1\)的都加入，那么两轮就会让\(r\)翻倍(并且很松)。用树套树支持单点修改，查询区间内\(\leq\)某数的数的和，就可以做到\(O(q\log^2 n\log v)\)了!
考虑把值域分成\(\log\)块，每一块是\([2^i,2^{i+1})\)。然后你发现，如果一块里面的\(\min\)被加入了，那么整个块都会被加入。这样就可以开一棵线段树，每个区间维护一下这\(\log\)块的和和\(\min\)，然后查询的时候先合并一遍，再爆力跳即可。复杂度是\(O(n\log v+q\log n\log v)\)。
dsq说可以用\(d\)叉树做到\(O(n+q\log^2 n/\log\log n)\)，空间可以把底层改成分块做到线性，但是我都不会/cy
T2
这玩意有点牛逼了（
收录于 ode和组合计数。
qc
T1
原题xxi poi R2 Superkomputer。收录于 oi题选做，以下内容仅作备份。
给一棵树，你一开始只占领了\(1\)号点，每次可以扩展与占领区域相邻的\(k\)个点，问最少多少次可以占领整棵树，对于\(k=1,...,n\)都求出答案。\(n\leq 10^6\)。
呃这个看起来是个合并的过程，考虑\(u\)，首先它需要往每个子树点一炮，然后子树们需要归并起来，有些操作有先后顺序，也就是扩展儿子之前需要先扩展父亲，最后我们在根的序列上每一步选\(k\)个，不能选冲突的。
于是这让我们想起来一个牛逼经典题，我忘了是哪个题了（
不过没关系的。首先我们需要考虑一个最佳的归并顺序，感觉了一下这个归并顺序可能是随\(k\)变化的/jy
不要着急断言，考虑先分析点性质吧。但是考虑了一会你发现这个归并性质并不是很好。如果你硬想出来了当我没说（
考虑我们时间倒流，每次可以删掉\(k\)个叶子，问最少多少次才能删到只剩根。
于是我们希望先删掉那些父亲只有它一个儿子的叶子，因为删它一定不劣。注意到删完之后叶子个数必然不增，于是每次删的只会越来越少。这个时间倒流好像很有效，但是如何才能提醒自己有意去时间倒流呢(好像只需要强行记住就可以了，但是我总是记不住¿)?
于是我们猜一个结论，每次删掉父亲度数前\(k\)小的叶子，如果不足\(k\)个则不删。然后这个贪心看起来并不是很真。没想法了，看看题解（
匪夷所思。考虑一个牛逼想法，我们扩展到足够深之后，可用的点数就会很多了，于是考虑一个牛逼策略，最优解必然是对于某一个\(d\)，前\(d\)层用恰好\(d\)次扩展完，而后面每次都能扩展\(k\)个点。
所有满足这个条件的\(d\)，给出的答案是相同的。
于是现在我们可以对于某个\(k\)求解了。注意到一个\(d\)确定了之后，答案就是，设\(d\)层以下的点数是\(c_d\)，就是\(d+\frac{c_d}{k}\)。
那么怎么知道一个\(d\)是不是满足上面的要求呢?注意到一个\(d\)如果错了，只可能是把答案算小了，而必然有一个会把答案算对，于是我们只需要全部取\(\max\)。
然后就很有趣了。这里只有一个取整，我们直接求\(\max(d+\frac{c_d}{k})\)，这玩意看起来是个凸壳，求一下在上面双指针扫即可。
qc表示这看起来是奇怪的斜率优化，但是我觉得它确实只是个凸壳（
难度基本在于猜策略吧/yun，感觉很玄幻。
T2
你有若干种法术，每个有一个伤害\(x\)和一个法力消耗\(y\)，你每次攻击可以使用\(m\)的法力，也就是说你最多攻击\(\frac{m}{y}\)单位时间，每单位时间造成\(x\)的伤害。
会有一些敌人，每个敌人一个血量\(h\)和一个时间\(t\)，表示你需要对他造成\(h\)单位的伤害，并且最多用\(t\)单位时间，过了这个时间他就蹬鼻子上脸把你干穿了。
接下来会有若干个事件，每个是 你学会了新法术 或者 有一个敌人来了，请你对于每个敌人求出你能不能一击干掉他。\(n\leq 10^6\)。注意\(m\)是一开始就给出，而不是每次询问都给出的(，但是后者也能做?)。
一个法术可以支撑\(\min(\frac{m}{y},t)\)单位时间，并造成\(x\min(\frac{m}{y},t)\)的伤害。
考虑对这个\(\min\)进行讨论，我们按照\(\frac{m}{y}\)排序，那么能打空法力的是一个后缀，二分一下，然后求一个最大的伤害。能打空的部分预处理，不能打空的部分直接\(xt\)。
但是qc给的做法好像比较复杂?可能我理解错题了（
T3
原题cf1487G。
有\(20\)种字符各\(c_1,...,c_{20}\)个，你要把它们排成一个长\(n\)的串，不能存在非平凡奇回文子串，求方案数膜\(998244353\)。\(n\leq 400,\frac{n}{3}\leq c_i\leq n\)，3s。
注意到非平凡奇回文子串一定包含长\(3\)的回文子串，于是只需要对它进行dp。
但是我们需要处理字符的个数。这就很惊悚了。
注意到有个奇怪性质\(c_i\geq\frac{n}{3}\)，这说明什么?
考虑有没有什么牛逼想法，注意到只有两种字符出现次数可以超过\(\frac{n}{3}\)，于是我们枚举这两种，在状态中只需要记录它们的数量，只要它们超了别的就不可能会超。dp是五维的(还需要记前两个字符)，于是复杂度是\(O(20^4n^3)\)。看起来完全过不去。
考虑会不会实际上只有一种字符出现次数超过\(\frac{n}{3}\)。可以构造出一个110011001100这样的东西，这两种字符出现次数都超过\(\frac{n}{3}\)了。
有什么办法呢?考虑一下我们希望优化到什么程度，理想的应该是\(O(20^2n^3)\)之类的，因为看起来我们并不能砍去一个\(n\)。
注意到奇数位和偶数位是独立的，这就很好，于是我们可以dp一遍自己卷自己，这样我们只需要记录一个字符，复杂度变为\(O(20^3n^3)\)。
然后你发现我们也不需要记录这个字符具体是哪个，只需要记录它是被枚举超了的中的哪一个，或者它没有超，复杂度变为\(O(20^2n^3)\)。
此时需要滚，空间是\(O(n^2)\)。
但是算量是3e9不是很受得了，不过它已经可以通过75pts（
注意到如果一个字符出现次数超过\(\frac{n}{2}\)次，那么它必然会和自己拼一个回文，于是就死掉了。于是我们dp的两维都获得了一个\(\frac{1}{2}\)的常数，整个就是\(\frac{1}{4}\)的常数，还可以rush。