感觉再不写做题记录会废的
这个博客用惯了，懒得再用原来那个写了
Latex不是很会，应该会比较乱
- CF1995D
首先可以转化一下题意，变成先选出一个字符集（必须包含字符串的最后一个字母），使得字符集里的字母在字符串中的位置前后相差不超过k，询问字符集的大小最小为多少
加上字符集<=18，这个时候应该能想到跟二进制枚举相关。但枚举符合条件的情况复杂度要炸，于是我们考虑不符合条件的情况，即某一段连续k个字符都不在我们枚举的字符集中，这时这个字符集就是不合法的，那么对于每一段连续的k个字符我们都把它用二进制表示出来，记录到数组里面，表示同时没有这些字符的字符集是不合法的，接着我们在记录的数组里做一个高维前缀和，最后二进制枚举每一个没被标记的点，用ans对他们1的个数取min，这道题就做完了
- P3899
答案由两部分构成
-
b在a的上面，此时可以直接算: \(\min (K,depth[a]) \cdot size[a]\)
-
b在a的下面，每个点以dfn为root下标,dep为树内下标开一颗线段树（动态开点），遍历树的时候把它变成一个类似前缀和的东西，即dfn[u]的树以dfn[u]-1的树为基础构建，然后询问直接回答root[dfn[p]+size[p]-1]的树减去root[dfn[p]-1]的树在dep[p]+1到dep[p]+K上的贡献即可。