打算今年上个Newbie（
所以来刷穿CF了，选了Rating 2600+，按通过人数降序。
然而发现刷不穿，甚至完全做不动。那就多见点经典题吧!
如果真有人想看这个的话，请结合CF的题库来阅读，当然选和我一样的tag。
如果做法只有几个意义不明的字，说明这题太简单或者太经典。
13E : 弹 飞 绵 羊
321E : 题意不是很清晰。
考虑直接dp，设\(dp(i,j)\)表示前\(i\)个人上\(j\)条船的最小代价，枚举最后多少个人上了最后一条船就可以转移。复杂度是\(O(kn^2)\)，无法接受。
发现满足四边形不等式，所以可以使用决策单调性分治，复杂度降为\(O(kn\log n)\)，可以通过。
还可以wqs二分，优化到\(O(n\log n\log k)\)，不过没有必要。
10D : L C I S
3D : 上古场评分偏高?
考虑一开始全搞成 ) ，然后从左往右扫，遇到不合法也就是 ) 多于 ( 那就把一些 ) 换成 ( ，于是我们计算换的代价增量也就是\(a_i-b_i\)，然后开一个堆维护前面最小的代价就好了。注意无解的情况。
那么这玩意是不是可以表示成网络流?
455D : 平衡树。
考虑每种值开一棵平衡树，维护这个值的所有编号并按下标排序，那么每次查询就是找到一棵树的一个区间，修改就是把最后一位的数拿出来重新插入到正确位置(其它的相对位置不会改变)。
发现并不容易维护查询所需的下标。我们可以考虑另开一棵平衡树维护编号——下标的对应关系，那么每次修改就是在这棵树上拿出来一个元素并重新插入，查询就是查rank。可以使用你喜欢的平衡树，复杂度是\(O(n+q\log^2 n)\)。
使用分块，可以获得小得多的代码复杂度。
622F : 拉插板子。
1344C : 好题。
先建图，从大的连向小的。
发现如果有\(i<j\)并且\(i,j\)有边，不妨假设\(x_i<x_j\)，那么我们可以填\(\forall x_i,\exists x_j,x_i<x_j\)或者\(\exists x_i,\exists x_j,x_i<x_j\)，但是不能填\(\forall x_i,\forall x_j,x_i<x_j\)或者\(\exists x_i,\forall x_j,x_i<x_j\)。\(x_i>x_j\)同理。
所以得到做法 : 一个点可以填\(\forall\)，当且仅当所有和它有偏序关系的点，也就是它能到达的和能到达它的点，编号都比它大。
怎么求这样的点?实际上我们可以只求出来最小的，这个可以记搜搞定。
631E : 简单题。
枚举每个数，考虑把它移到哪里去。
显然要对往前往后分开讨论，我们不妨先考虑往前。
发现中间那些数的贡献可以用前缀和简单表示出来，如果我们把\(i\)移动到\(j\)，那么价值变化量是\((i-j)a_i+s_{i-1}-s_{j-1}\)，拆开得到\(ia_i+s_{i-1}-s_{j-1}-ja_i\)，去掉与\(j\)无关的项，发现是一个关于\(a_i\)的一次函数，可以用李超树维护。反着是类似的。
1325E : 妙题。
每个数的因数个数不超过7，说明什么?
质因数个数不超过\(2\)。我们先给所有次数模\(2\)，然后建一张图，每条边连接每个数的两个质因数。这样一个环就表示一个方案。
只有一个质因数怎么办?可以连向\(1\)。
然后就变成了无向无权图最小环，Floyd绝对没前途，直接bfs可以做到\(O(n^2)\)。
考虑如何优化。因为每个数的两个质因子乘起来不超过1e6，所以我们得到的图在远处会比较稀疏。
如果两个数都超过了1e3，那么它们不可能有边，所以每个环上一定有一个1e3以内的点，所以只需枚举到1e3即可。复杂度\(O(\frac{n\sqrt{v}}{\log v})\)。
6D : 显然可以爆搜。
更好的做法是进行dp，设\(dp(i,j,k)\)表示干掉了前\(i-1\)个人，第\(i-1\)个打了\(j\)发，第\(i\)个打了\(k\)发，最小的总发数。转移枚举第\(i-2\)个人打了多少发。
555E : 不会边双。收录进 连通性相关问题。
613D : 消 耗 战
1110F : 这个性质就很迷惑。
当然可以爆力点分治。
有个好玩的做法，说的是发现询问的叶子区间在dfn上也是区间。考虑直接维护这个答案，我们离线下来dfs这棵树，每次从一个点走到儿子的贡献就是给子树里面的点都减去这条边的边权，子树外面的加上边权；反之亦然。所以我们拿线段树维护所有叶子，然后支持区间加减区间\(\min\)即可。
715C : 点分治。
考虑如何合并，如果一条\(u\)到分治中心、数值为\(x\)的路径和分治中心到\(v\)、数值为\(y\)的路径拼起来膜\(m\)得\(0\)，则有\((x\cdot10^{\mathrm{len}(y)}+y)\bmod{m}=0\)，移项得到\(x\equiv -y\cdot 10^{-\mathrm{len}(y)}\pmod{m}\)，然后因为\(10\perp m\)，那个逆元可以exgcd，就做完了。
383E : 子集前缀和。
有一个不好，我们算一个都没有的方案数。
容易想到把是不是元音字母表示成一个二进制状压的集合，然后一个都没有说的就是选的元音字母是串中没有的字母的子集，于是我们可以愉快的直接上子集前缀和了。
741D : 重新排列可以变成回文串，等价于最多一个字符出现一次。
用二进制把每个字符的出现次数压起来，那么出现两次可以消去，于是我们可以用异或表示路径合并。
先差分一下试试，设\(f(u)\)表示\(u\)到根路径的上面的状压的结果，那么\(u,v\)合法当且仅当\(\mathrm{popcnt}(f(u)\operatorname{xor}f(v))\leq 1\)。
然后你发现一共只有\(23\)种可能的状态是合法的，也就是全\(0\)和有一个\(1\)。爆力枚举这些情况。
考虑一个点的答案比它儿子们答案的\(\max\)多的部分就是它作为\(\mathrm{lca}\)的部分，所以我们用\(\mathrm{dist}\)的公式，于是可以开一堆桶存每个状态的最大\(\mathrm{dep}\)。
直接枚举一个情况，然后枚举一个点找另一个点，复杂度是\(O(n^2\sigma)\)。
考虑树上启发式合并或者说静态链分治，我们每次拿着一棵轻子树去当前的数据结构中查，查完了合并进来，这样复杂度就是\(O(n\log n\sigma)\)了。
662C : 看到这个\(20\)的数据范围你就想到爆搜，但是怎么搜?
呃我们枚举每一行的翻转情况，翻完行之后考虑一列如果\(1\)超过一半那么它翻，否则它不翻。这样它最后的贡献就是\(01\)个数的较小值。
我们设\(f(x)\)表示二进制状态\(x\)中\(01\)个数的较小值，这个东西很容易计算。
考虑写一个式子，设\(a_i\)表示每列的情况，枚举\(b\)表示行翻转的情况，设这种情况下的答案是\(Ans(b)\)，那么我们得到
\[Ans(b)=\sum_{i=1}^n f(a_i\operatorname{xor}b)\]好像一个异或卷积?我们设\(c_i\)表示\(a_j=i\)的\(j\)个数，就变成
\[Ans(b)=\sum_{i} c_if(i\operatorname{xor}b)\]然后你发现\(Ans\)是\(c\)和\(f\)的异或卷积，法哇塔就完了。
896C : 经典。
932F : 李超树合并优化dp，经典。
19D : 直接线段树分治。
1439C : 不错题。
考虑每一段连续的购买，一个结论是每段之后手里的钱至少少一半，因此段数是\(O(\log v)\)。
考虑一段的结尾，设这一段长度是\(s\)，这一段后面第一个是\(t\)，拿着\(y\)元，那么显然有
\[\begin{aligned} y&\geq s\\ y-s&<t\\ t\leq s \end{aligned}\]然后要证的就是\(2(y-s)\leq y\)。
\[\begin{aligned} 2(y-s)&\leq y\\ 2y-2s&\leq y\\ y&\leq 2s\\ y-s&\leq s\\ y-s&\leq t \end{aligned}\]然后就证完了。如何找到这些区间?
考虑一个类似于吉老师线段树的做法，我们线段树每个点维护区间最小值和区间和。
进入一个结点的时候，
-
如果区间最小值都买不动，直接返回
-
否则，如果可以买完整个区间，更新答案，直接返回
-
否则，递归到左右儿子
。我们每一段连续的购买的代价显然都是\(O(\log n)\)，所以我们得到了一个\(O(\log n\log v)\)单次的上界。实际上这个界很松。
修改就随便做了，改变的一定是一段区间，二分左端点然后推平即可。
我居然写了代码，在这里。
2C : Fucking computational geometry.
1375G : 已经收录于 cf思维题选㗅 和 换根dp。
438E : 小朋友和二叉树!
235C :
SAM支持从模式串前面删字符，所以破环成链，拿一个滑动窗口去扫即可。
具体怎么删?
考虑SAM每个点匹配的是它里面 最长子串 的满足 长度在某个值以上 的所有 后缀。具体一点，这个 某个值 就是\(\mathrm{maxlen}(\mathrm{parent}(u))+1\)。
那么删掉最前面的字符得到的串，一定是删之前串的后缀，所以如果状态变化了，一定是因为长度太短，跳到了\(\mathrm{parent}\)。判断一下就好了。
注意题意说的是文本串中每个子串只算一次，所以我们需要给走过的点打上标记，如果重复走了那就不再计入答案。
这里有个实现的小trick，就是vis数组存储的是上一次被标记时是在第几次询问，然后vis[u]=1变成vis[u]=当前询问编号，就可以实现简单的清空。
527E :
考虑如果入度出度都是偶数，那么总度数是偶数，那么有欧拉回路。
我们先把度数是奇数的点配对连边，然后这个图就有欧拉回路了。
考虑如果我们让回路上相邻两条边定向相反，那么这两边之间的点要么被贡献\(2\)的入度，要么是\(2\)的出度，这样最后一定是偶数。
但是如果这个欧拉回路是奇环，也就是总边数是奇数，那我们就没法这么定向了。此时随便选一个点加一个自环即可。
1406E : 有趣题。
1e5以内有多少个质数?打个表你发现是9592。这可真不少?
一个最简单的做法是，我们直接枚举每一个质数，删掉它的倍数，然后再查询它的倍数个数；同时模拟没有\(x\)的删数过程，如果输出有不同，说明\(x\)具有当前删的质数作为质因子。
这样操作次数是2*9592+1，并且我们还没考虑质因子的次数呢，这不太行。
考虑这个删的过程有很多是没啥用的，因为我们实际上只需要sqrt(1e5)=316以内，前65个质数就可以筛掉1e5以内所有合数。同时，在后面这9527=9592-65个质数中，\(x\)最多只可能包含一个作为质因子，并且次数一定是\(1\)。不妨先考虑这些大质数。
发现尽管只可能包含一个，我们还是不得不全删一遍。
考虑一个分块，我们把这些大质数分成根号块，每次删光一块然后查询1的倍数个数，就可以得知\(x\)是否包含这一块的质数。如果包含，那么我们就重新一个一个枚举这一块里的质数进行查询。如果每98个一块，一共有98块，总共查询次数是9527(每个质数删一次)+98(每块查一次1的倍数个数)+98(暴力遍历一块)=9723。还剩276次(除去最后的回答)。
对于小质数，我们删光它们，然后暴力枚举质数幂查询来尝试分解。316以内有147个质数幂，我们的询问次数是65+147=212。最后总询问次数是9936，卡的真紧啊!
940F : zrz秒了啊!
考虑答案是根号阶的。最坏情况下出现次数是\(1,2,3,...\)，这样大约\(\sqrt{2n}\)项加起来就会超过\(n\)，这是一个自然根号。
然后就变成了，\(O(1)\)查询区间中有没有出现恰好\(k\)次的数，\(O(\sqrt{n})\)单点修改。
看到这个单点修改复杂度肯定先考虑分块。然后你发现并不是很好直接统计那个查询所需的信息，因为数很多。
想了114514年你发现还是不会做……然后去看题解。
这**是个带修莫队?CF真是奇迹oj，4s 1e5 \(O(n^{\frac{5}{3}})\)随便跑（
想940F的时候我查了查静态区间mex怎么做，发现做法还挺好玩。
从左往右扫序列，维护\(last(i)\)表示数\(i\)最后一次出现的位置，那么每次加入一个数只会改变一个数的\(last\)，可以用主席树维护。
然后每次询问我们找到右端点对应的版本，二分出最小的\(k\)使得\(last(k)<l\)，这个可以通过维护区间\(\min\)实现。
从这里开始是通过人数1000-了。可能将来会变化（
1208F : 位运算真是奇妙。完全不会。
这题的技巧，在CF上一篇著名的blog称其为SOS dp(Sum Over Subsets dp)，不过硬要说就是子集前缀和一类的东西。
枚举一个\(i\)，然后从高到低按位贪心，维护一个当前最优的\(s=a_j\operatorname{and}a_k\)。这个\(s\)的含义是，存在一个\(a_j\operatorname{and}a_k\)包含\(s\)。
如果\(a_i\)这一位是\(1\)，那么\(s\)这一位是\(0,1\)都随意。根据\(s\)的含义直接赋\(0\)即可。
如果\(a_i\)这一位是\(0\)，那么我们希望\(s\)这一位是\(1\)。
所以我们的问题变成快速检查一个\(s\)是否可行，也就是是否存在一个\(a_j\operatorname{and}a_k\)包含\(s\)。
容易想到做一个位运算卷积，我们做一个fwt-and即可。
但是这里还有一个限制，也就是\(i<j<k\)。发现我们可以做子集后缀和的时候直接维护这一状态最大的\(j,k\)，这就非常好。
1416D : 简单题。
考虑删边连通性的经典性质，也就是删除时间的最大生成树连通性和原图连通性相同。
所以我们可以把这个问题转成树上问题。
然后每次Extract-max操作就是找到路径瓶颈大于当前值的所有点，你发现这是Kru重构树上的一棵子树，建立Kru重构树然后线段树维护即可。
364D : 你发现这个数据范围并不能全做一遍质因数分解。
那怎么办呢?不会办。
去看了一眼题解，知道是随机算法没有$途!
核心是，每个数有\(\frac{1}{2}\)的概率在最优方案中被选中。这就很适合随机化。
考虑如果知道了一个数\(x\)在最优方案中被选中了，那么答案一定是这个数的因数。我们分解因数，然后求一遍这个数和所有数的\(\gcd\)，复杂度是\(O(\sqrt{v}+n\log v)\)，其中\(d(v)\)是\(v\)以内最大的\(d\)，大约是6000。有点慢?不过CF 4s那还可以接受。
然后我们得到一个数组\(c\)，\(c(i)\)表示\(x\)的第\(i\)个因数在那一堆\(\gcd\)里面出现了几次。做一遍因数后缀和，也就是求出\(f(d)=\sum_{d\vert n}c(n)\)，这个可以很容易地写出一个\(O(d^2(v))\)的暴力。然后求出最大的\(d\)满足\(f(d)\)至少是一半即可。
跑10遍，刚好不会T飞。
547E : 重工业。
对这一大串模式串建立ACAM，然后把文本串一个一个拿上去匹配。
回忆一下只有一个文本串怎么做。我们每次做一个到根的链加。
那么这里有区间的限制了，我们就不能直接加了，我们需要每个点开一个数组维护每一个文本串加了什么。
这个数组有两种搞法，一种是离线差分之后变成前缀信息，然后用线段树或BiT维护；一种是打上标记最后线段树合并。就做完了。
我不喜欢离线，所以写了第二种（
1270G : 收录于 CF思维题选㗅。
750E : 收录于 ddp。
1439B : 收录于 CF思维题选㗅。
526F : 草，没看到是排列?
先按横坐标排序，我们得到一个数组，称为\(y\)好了。
考虑之前的限制，现在就是\(r-l+1=k\)且\(\max(y_i)-\min(y_i)+1=k\)，也就是\(r-l=\max(y_i)-\min(y_i)\)。
这就非常好，看到\(\min,\max\)你立马就能想到笛卡尔树。
我们进行启发式分裂，每次找到最小值分成两半，枚举小的一边，用类楼房重建线段树维护另一边。呃具体地，calc(u,k,x)表示左边有前缀最大值\(k\)，求\(\max-r=x\)的个数。这样可以做到\(O(n\log^3 n)\)，实在是拖拉机，并且是瞎扯的还不一定正确。
这是我和zrz的一点想法。
首先这个启发式分裂+类楼房重建线段树就很奇怪，我们直接看题解。(语无伦次)
题解给了三种做法，分治，以及线段树+单调栈。
分治好!我们分两种情况讨论。讲的可能不是很清楚。
考虑四个数组\(leftmax,leftmin,rightmax,rightmin\)，大家懂的都懂。
- 最大/最小值在同侧，不妨假设在左边
限制是\(leftmax_l-leftmin_r=r-l\)，并且\(leftmax_l\geq rightmax_r,leftmin_l\leq rightmin_r\)。
我们可以扫这俩所在的那一边，不妨假设是左边，然后同时扫右边，维护满足第二个限制的最右右端点。
然后按照第一个限制求出右端点，如果这个右端点在上面的右指针以内那么合法。
- 最大/最小值在异侧，不妨假设最大值在左边
限制是\(leftmax_l-rightmin_r=r-l\)，并且\(leftmax_l\geq rightmax_r,leftmin_l\geq rightmin_r\)。
第一个限制移项可得\(leftmax_l+l=rightmin_r+r\)。
枚举一个左端点，发现第二个限制中，前半部分表示的是右半边的一个前缀，后半部分是一个后缀，所以可行的右端点是一个区间。
所以我们同时维护这个区间，把区间中所有点的\(rightmax_r+r\)扔进一个桶，每次直接查询有多少个可行的。three pointers
这个玄学分治复杂度就是\(O(n\log n)\)。
加强版是997E，静态区间查询。这个分治法好像不是很能扩展到那里去?
考虑直接枚举右端点，然后用线段树维护每个左端点到右端点的\((\max-\min)-(r-l)\)。为什么是枚举右端点?因为要从左往右扫的话，右端点右移是增加，左移是删除，而\(\min/\max\)不容易删除。
我们要维护的东西就非常好 : 它是非负的。线段树每个点维护最小值和最小值个数即可。
然后右移一次会更新一堆\(\min,\max\)，可以用单调栈求出影响的区间，然后直接推平即可。注意每次进出栈会带来一次线段树操作，所以复杂度是\(O(n\log n)\)。
1391E : 收录于 CF思维题选㗅。
1370F2 : 我以为是3F，结果是2F?
首先一看就知道询问次数是\(\lceil\lg n\rceil+1\)。
做法挺奇妙的。
先问一次所有点，就可以得到一个位于两个特殊点路径上的点，以及这个路径的长度\(l\)。不妨称为特殊路径。这需要\(1\)次询问。
考虑以这个点为根dfs，我们就得到了两个特殊点深度和的限制。
二分较深的点的深度，我们每次询问所有深度为\(mid\)的点，如果有一个点在特殊路径上，那么我们得到的距离就是特殊路径长度，否则是别的东西。画一个图就会很好理解为什么要二分。这个询问次数是\(\lceil\lg n\rceil\)。
然后我们需要一次询问获得较深的点，然后再一次询问就可以获得较浅的点。这样询问次数总共是\(\lceil\lg n\rceil+3\)。
哪里可以砍掉两次询问?
-
打表发现，二分过程中肯定会询问到较深的特殊点，所以我们二分出深度之后可以直接获得较深的特殊点。
-
较深的特殊点的深度上界是\(l\)，而下界不必是\(0\)，可以是\(\lceil\frac{l}{2}\rceil\)，这样省去了一次二分。
于是总询问次数就是\(\lceil\lg n\rceil+1\)，可以通过。
906D : 扩展欧拉定理。
扩展欧拉定理用于在模合数时，代替费马小定理给指数取模。
知道这个的话，区间长度可以直接砍到\(\log v\)的级别，直接暴力即可。
注意每次求一堆\(\varphi\)的复杂度不能承受，我们可以直接预处理\(\varphi(p),\varphi(\varphi(p)),...\)。
复杂度是\(O(n\log v)\)。
17E : 完全不会。
考虑Manacher求出回文子串数量，然后用总对数减去不相交的对数。
不相交的对数是什么?如果\(r_s<l_t\)，那么\(s,t\)不相交。
我们枚举一个\(r\)，计算有多少个回文子串的\(l\)在它右边。发现Manacher中每个位置统计到的回文子串长度是一个区间，左端点也是一个区间，所以我们可以用差分-前缀和来支持这个区间加。刚才要的东西就是这个的后缀和。
复杂度\(O(n)\)。
为什么会有把相交变成不相交的想法?相交有八个条件，不相交只有一个条件(因为只对于左边的统计右边的)。
19E : 有意思。
考虑删掉一条边变成二分图，要么是本来就是二分图，要么是删掉这一条边的时候所有奇环都没了。
所以如果我们可以求出所有奇环的交，就很好了。
然后我就想起来一道题叫 SP2878/UVA1364 Knights of the Round Table。这个题的结论说的是一个边双里面如果有奇环，那么每个点都在一个奇环中。于是我就在奇怪的思路上越走越远!然后就去看题解了。
先随便跑一棵dfs树，然后对于每条非树边，它确定了一个环。
这些环我们称为 基本环(称呼并不广泛，不过在你谷有12个人给这篇题解点了赞)。不同的dfs顺序可能得到不同的基本环，不过没有关系。
[WC2011] 最大XOR和路径 指出，定理 每个简单环都是若干基本环的对称差。
证明 考虑一个简单环经过的所有非树边，它们确定的基本环的对称差就是这个环。需要一点想象力。
同时我们有这样的推论 : 每个非简单环都是若干简单环的并，所以它们都是若干基本环的并和对称差。
然后可以从一条路径开始，这样对称差得到两点间所有简单路径。
这个结论经常用于 无向图，简单路径 和 异或 相关问题。
定理 如果没有奇基本环，那么没有奇环。
证明 没有奇基本环，说明每条非树边端点都不同色，而每条树边端点已经不同色了，所以说明可以二分图染色，也就是没有奇环。
所以如果没有奇基本环，直接输出\(0\)。如果只有一个奇基本环，那么我们随便删一条边就好了。
如果有很多奇基本环，刚才我们就知道需要求出所有奇环的交。
所有奇环的交一定是所有奇基本环的交，但是这不够充分，我们需要继续考虑删掉奇基本环的一条边还有奇环的情况。
容易想到删一条边只可能对经过它的基本环产生影响。
画画图发现只有一种情况 : 一个奇基本环和一个偶基本环同时经过这条边时，这条边删了还是会有奇环。
所以我们分开统计奇偶，对每个基本环做一个树上的链加，最后没有被偶基本环加并且被所有奇基本环加了的边就是答案。
其实这个题大家都见过，就是线段树分治板子题 二分图 啊!
实际上不用线段树分治，可以直接用cdq分治做，类似 消失之物。
据说dfs树是解决环相关问题的利器，哪天整理一下。
650D : 说起来我之前还扯过一个静态区间LIS的莫队，好像也假了/kk
先把LIS抽象成平面上的问题，然后这个我们预处理\(pre,suf\)分别表示从每个位置开始的前后缀LIS，就变成了矩形max，主席树或者离线BiT都可以。
另外区间lis是蒙日阵的经典应用。
487E : T o u r i s t s
1446D1 : 这个题一看就知道复杂度是\(O(nv+v^3)\)之类的东西。
有个我想不到的结论 : 答案区间中的众数们，其中一定有至少一个是整个序列的众数。当然这是众数唯一的情况，众数不唯一直接输出\(n\)。
证明很简单，如果不是的话，我们进行调整，不断扩大这个区间，整个序列的众数在区间中的出现次数一定会反超区间中原有的所有数，那么我们找到区间中众数出现次数和整个序列众数在区间中出现次数这个两个函数的交点，那里的区间合法并且更长。
\(v\)是这么的小!我们考虑直接枚举另一个众数。
枚举之后，每个数只有三种情况 : 是整个序列的众数，是枚举的数，是别的数。我们要做的就是找一个最长的区间使得前两种数量相同。
第三种不用管，因为用与刚才的结论类似的证法可以证明，我们这样扩展下去会得到一个更长的区间，以第三种那个数作为第二个众数。
当然考虑把整个序列的众数全改成\(-1\)，枚举的数改成\(1\)，别的改成\(0\)，问题转化成最长的和为\(0\)的区间。前缀和，然后开一堆桶，每个桶存下标的\(\min\)。复杂度\(O(nv)\)。
1446D2 : 值域变大了，怎么办?
不管值域多大，刚才的结论还是正确的。
枚举一个数不一定还有前途了，因为我们的枚举看起来很难改进，数据结构维护想了想好像十分困难，分块也分不动。
考虑一个枚举，我们枚举全局众数的出现次数\(t\)!然后用双指针去扫，对每个\(l\)求出最大的\(r\)使得区间中没有出现次数超过\(t\)的数。同时我们维护一个计数数组，看一看有没有出现恰好\(t\)次的数，如果有就拿去更新答案。
这东西是\(O(n^2)\)的，不过你发现这两个算法好像有点互补。进行根号分治，对于出现次数超过\(B=\Theta(\sqrt{n})\)的数我们跑Easy中的算法，对于出现次数不超过\(B\)的我们跑上面这个算法，复杂度就是\(O(n\sqrt{n})\)了。
700C : 一眼最小割+wqs二分。看起来跑不过并且不一定对。
你仔细看!发现复杂度是\(O(nm)\)!
但是枚举一条边，另一条求割边是不行的，因为这样是\(O(m^2)\)。
考虑求出一条\(s\rightsquigarrow t\)，那么这条路径上一定有至少一条边要割，我们枚举这条边然后跑割边就行了，复杂度\(O(nm)\)。
1363F : 考虑这个操作实际上干了这么一件事 : 把一个字符插入到前面。
考虑一个dp，我们设\(dp(i,j)\)表示\(s\)的前\(i\)个字符加上\(j-i\)个操作过来的字符，匹配\(t\)的前\(j\)个字符的最小操作次数。
考虑转移，我们枚举第\(j\)个字符怎么来的 :
-
从前\(i\)个字符挤过来。那么一定是第\(i\)个，所以条件是\(s_i=t_j\)，\(dp(i,j):=\min(dp(i,j),dp(i-1,j-1))\)
-
从后面操作过来。那么我们随便选一个，条件是后面有一个\(t_j\)，\(dp(i,j):=\min(dp(i,j),dp(i,j-1)+1)\)
-
往前移，把工作交给前面。\(dp(i,j):=\min(dp(i,j),dp(i-1,j)+1)\)
。你发现一个小问题，那就是往前移和后面移过来的其实是一个东西，但是我们计算了两次。这不好!所以我们去掉其中一个的\(+1\)即可，事实证明去掉哪一个都可以。
521D : 首先我们知道，操作顺序一定是赋值\(\rightarrow\)加法\(\rightarrow\)乘法。
先考虑乘法，因为求的是乘积最大，对一个数进行乘法相当于对最后的答案进行乘法，所以我们一定会选取最大的若干个乘法操作。
然后考虑赋值和加法。
首先赋值也是一种加法。
我们直接开个堆每次选取最优的。不过这个加法操作会更新一大堆加法操作!这就很不好。
实际上只有最大的那个加法操作有用，所以我们可以每次选了最大的之后把次大的扔进堆。这里不能比较答案，不过你发现三种操作都可以一个堆处理掉，所以就做完了，复杂度\(O(n\log n)\)。
576D : 众所周知1000才是Floyd的数据范围（恼
考虑如果\(d\)很小，那么分层图就好了。
但是\(d\)不小!
考虑实际上只有\(m\)层是新开辟了一些边，此后最多再有\(2m\)层就可以走完这次开辟的新边，为了奇怪的走法我们把它增加到\(3m\)，总之只有\(O(m^2)\)层是有用的，别的层中总是可以在一条边上来回走。bfs即可，复杂度\(O(m^3)\)，不过没写，不知道正确性。
正解是矩阵快速幂+倍增。每次我们尝试一直走到下一条边开放，如果在此之前就能到达我们就倍增找到最短时间，否则继续尝试走到再下一条边开放。用bitset存储矩阵，复杂度是\(O(\frac{n^3m}{w}\log v)\)。
1278F : 这个\(x^k\)来者不善。
直接写式子!
\[\sum_{x=0}^nx^k\binom{n}{x}\left(\frac{1}{m}\right)^x\left(1-\frac{1}{m}\right)^{n-x}\]然后考虑怎么算。这个\(n\)大上天了啊!
不过这让你想起一道题叫 组合数问题，或者 如何优雅地求和。那个题也是\(n\)大上天，但是\(k\)很小啊!
我们硬推!
\[\begin{aligned} &\sum_{x=0}^nx^k\binom{n}{x}\left(\frac{1}{m}\right)^x\left(1-\frac{1}{m}\right)^{n-x}\\ =&\sum_{x=0}^n\sum_{i=0}^k{k\brace i}x^\underline{i}\binom{n}{x}\left(\frac{1}{m}\right)^x\left(1-\frac{1}{m}\right)^{n-x}\\ =&\sum_{i=0}^k{k\brace i}n^\underline{i}\sum_{x=0}^n\binom{n-i}{x-i}\left(\frac{1}{m}\right)^x\left(1-\frac{1}{m}\right)^{n-x}\\ =&\sum_{i=0}^k{k\brace i}n^\underline{i}\sum_{x=0}^{n-i}\binom{n-i}{x}\left(\frac{1}{m}\right)^{x+i}\left(1-\frac{1}{m}\right)^{n-x-i}\\ =&\sum_{i=0}^k{k\brace i}n^\underline{i}\left(\frac{1}{m}\right)^i\sum_{x=0}^{n-i}\binom{n-i}{x}\left(\frac{1}{m}\right)^x\left(1-\frac{1}{m}\right)^{n-i-x}\\ =&\sum_{i=0}^k{k\brace i}n^\underline{i}\left(\frac{1}{m}\right)^i \end{aligned}\]就做完了，复杂度\(O(k^2)\)。利用带项式科技快速求一行斯特林数，可以做到\(O(k\log k)\)。鰰给出了一个\(O(k)\)做法，我不懂。
1523E : 看起来不是很能做/jk
呃草，我们可以枚举最后选了多少个，然后隔板法选一个方案数，随便算这么选的概率，乘起来就是选到这么多的总概率，然后这就单次\(O(n)\)了。这是二轮省集D8T1的弱化版。
516D : 半个一眼题。
一个显然的、不用任何性质的做法是，直接双指针扫过去，用一个LCT维护最大连通块大小。这个看起来并不能过……除非你的LCT足够快。
发现每个点出现是一个区间，于是考虑线段树分治，还是过不了。
看起来必须要发掘这个\(f\)的性质了。你发现它的最大值在叶子、最小值在直径中点取到。这是废话。
看题解去了/ll
呃你发现如果选中了一个连通块，最小值一定在直径上取到。我们可以对每个点二分求出它到直径上哪一段区间有贡献，然后你发现可以提前排序双指针而省去二分，就单次线性了。
240F : 直接连续段均摊。感觉好像在哪做过?
呃等等，这里有一个问题，就是怎么判断能不能拼成回文串。操作没有进行也split是不影响复杂度的，所以我们可以在操作区间左右端点进行split，然后用维护连续段的平衡树顺便维护一下区间能不能拼成回文串这个信息，也就是维护merge之后的字符桶。复杂度是\(O(n\Sigma\log n)\)，平衡树常数略大可能并不能过/jk
也有线段树做法。我们开26棵线段树，然后就\(O(n\Sigma\log n)\)了，常数远小于平衡树……
163E : 直接二进制分组/线段树分治。
有一个直接使用ACAM的做法。考虑查询就是fail树上若干次子树和，修改就是单点修改，这个可以dfs序+BiT维护。
293E : 直接点分治。
666E : 一眼题，然而需要比较熟练的SAM技巧。
我去年就忘了。ACAM处理 一个串里面找一堆串，广义SAM处理 一堆串里面找一个串。具体处理方式是，拿着那一个串上去走，每一步做一个fail树/parent树上到根的链加。
子串太多了，所以我们选择后者，也就是对\(t\)们建立广义SAM。然后拿着\(s\)上去跑，每一步做一个parent树到根的链加，每个\(t\)被匹配的次数就是它终止结点的值，可以差分之后线段树合并搞定。
呃考虑\(s\)的一个子串怎么做。我们当然离线扫描线，对于每个\(r\)，我们要找到\([l,r]\)匹配的结点，然后直接在它的线段树上查。你发现这个东西一定在\([1,r]\)匹配的结点的祖先，可以倍增一下搞定(呃根据\(\mathrm{maxlen}\)判断)，就做完了。
724E : 收录于某轮省集，我也忘了（
258D : 二轮省集，lyh是不是讲过这个啊……
那我也不会，看题解去。
考虑直接设\(f_{i,j}\)表示\(a_i>a_j\)的概率，然后每次修改都会改\(O(n)\)个并且改动易于计算。做完了/jk
1301F : 看到这个还是考虑分治，但是，呃你发现这个同色直接传送不好搞，分治处理不了这种奇怪的东西。
发现Floyd可以跑\(1000\)(所以看到\(1000\)图论一定要想Floyd)，所以我们可以考虑能不能用类似Floyd的东西跑一跑。我们枚举第一次传送是在哪个颜色，然后你就知道剩下的部分是一个 颜色到点的最短路。边是双向的，所以考虑处理 点到颜色的最短路。
呃然而这个东西听起来也不容易。我们考虑同时对每种颜色进行多源bfs，这样可以考虑颜色之间的相互传送，不过复杂度会变成\(O(nmk^2)\)，你就死了。
呃你发现很容易优化，因为某一轮已经传送到一个颜色之后，再传送到那个颜色就一定不优了，所以复杂度就是\(O(nmk)\)了。
848C : 1e5 6s，你觉得除了带修莫队还能是什么?
好了去看看题解，怎么有时间分治做法/jk
考虑我们完全可以拆开，变成两个东西的和，然后就变成动态二维数点了/jy
1495D : 和suxxsfe㗅掉了/cy
考虑枚举\(i,j\)，一个点\(k\)可以连向父亲\(l\)，当且仅当\(d(i,k)=d(i,l)+1,d(j,k)=d(j,l)+1\)。于是找到所有找父亲的方案，乘起来就好了。
755F : 考虑把排列分解为若干个环，然后每个人不带礼物，相当于把一条边两端的点全都ban掉。
最少 : 我们需要\(\lceil\frac{l}{2}\rceil\)个人不带礼物才能ban光一个环，所以可以先选偶环，选完了试图选不满奇环，最后再把奇环选满。
最多 : 考虑填满一些环，如果刚好填满那就太棒了，答案是\(n-k\)，否则我们需要选一条链，答案就是\(n-k-1\)。这个 填满 显然是需要背包的，但是1e6咋背包?
这里有个自然根号，不过直接用不是很舒服，所以考虑进行根号分治，对于小的二进制分组，对于大的直接跑，取阀值\(\Theta\left(\sqrt{\frac{n}{\log n}}\right)\)，复杂度是\(O(\frac{n\sqrt{n}}{w\sqrt{\log n}})\)，调一调参跑的飞快。另外我感觉可以有更好的复杂度?
1442D : 好眼熟……
考虑这相当于把一堆序列卷起来，但是min,+卷积复杂度不可接受。所以必须需要一点性质了。
你发现不降，但是这有啥用?
考虑这说明我们越取越优，也就是说每一个序列取得的结果都是凸的，所以做闵和就好了。复杂度\(O(nk)\)，咋想都是对的?
一看题解，是神仙结论/jy，但是题解没人闵和，哪天写一下/jk
你发现越取越大，所以如果我们决定取了一个序列，就一定会一直把它取完。我们枚举最后取的序列，剩下的都是要全取完的，变成了去掉每一个的背包，消失之物 即可。
908G : 显然是数位dp。但是数好大……
你发现我们可以记一下每个数的出现次数，这样剩下的情况就只有……\(\binom{709}{9}\)种了!这听起来很见鬼，还是算了。
看题解/ll
考虑我们把每个数拆开，求出\(f(i,j)\)表示有多少数排序后第\(i\)位是\(j\)，搞定这个就随便算答案了。
数位dp。我们考虑第\(i\)位是\(j\)，相当于有\(i-1\)位\(\geq j\)，\(t-i\)位\(\leq j\)，\(1\)位\(=j\)的方案数，但是这里看起来不好直接用组合数选出来进行拼接，因为可能有一车\(j\)……要是枚举有多少个\(j\)，复杂度又不能接受。
考虑拆开每个数码的贡献，我们枚举一个\(k\)，算有多少\(\geq k\)的。于是可以设\(dp(i,j,lim)\)表示前\(i\)位，有\(j\)位\(\geq k\)，懂的都懂的方案数。这样就是\(O(10^2n^2)\)。
可以做到\(O(10^2n)\)甚至\(O(10n)\)。
考虑还是把每个数拆开，我们直接对于每个数\(k\)统计它的贡献。
设\(dp(i,lim)\)表示考虑前\(i\)位，懂的都懂，所有数中\(k\)的贡献和。为了方便转移还需要记一个\(g(i,lim)\)表示往所有数中加一个\(k\)产生的贡献，剩下的就显然了。复杂度是\(O(10^2n)\)，\(O(10n)\)啥的我不会。
1223F : 你发现这个像极了括号序列……但是又不太一样……
完全不懂，看题解/ll
草，这就是 括号树。我死在智障题上两次/ll
我们枚举一个左端点，统计有多少右端点合法。现在问题是怎么求\(next\)，也就是和当前位置匹配的位置，搞定了这个就可以上括号树的dp了。
你发现直接扫过去匹配一遍是不行的，因为一个位置同时可能作为左右括号；你要是把\(next\)换成\(pre\)也会出现这个问题，不过位置是对称的。
考虑一个爆力方法，我们找到\(next_{i+1}\)，如果\(next_{i+1}+1\)这个位置和\(i\)同色那就好极了，不然我们继续找到\(next_{next_{i+1}+1}\)这样的。这当然是\(O(n^2)\)。
怎么优化?你发现这个过程就是一直从\(j\)跳到\(next_{j}+1\)，直到\(a_j=a_i\)。所以我们可以设\(f(x,y)\)表示从\(x\)出发一直跳到\(a_j=y\)会跳到哪里。然后这个\(f\)的转移，你发现我们每次只会改一个位置，剩下的位置可以直接继承过来，所以可以用主席树维护。
数据结构学傻了!你发现除了\(n+1\)，每个位置只会被继承一次，可以直接用map来做，它支持\(O(1)\)的swap。这本质上是说\(next\)构成了一棵树，我们是在遍历这棵树。
另一个简单做法是，考虑\([l,r]\)是匹配的，当且仅当我把\([1,l-1],[1,r]\)分别跑一遍，最后得到的状态相同。hash一下就好了。
1364E : \(4296\)是什么?
看起来是\(2\times 2048+200\)。
考虑如果我们找到\(0\)，那就万事大吉。我们有\(2249\)次操作可以做这件事。
这\(201\)次好像不仅仅是一点容错了。考虑如何才能快速减少数的数量。容易想到，如果我们找一个数\(t\)，查询所有数和它的\(\operatorname{or}\)，其中不是最小值的那些一定不是\(0\)。如果\(t\)的\(0\)位数足够多，达到了一半，我们就可以把值域折半，也就是说剩下的数只有不到\(32\)个了，这样进行\(\log\log v\)轮就会结束，当然实际上这么少的数你咋做都行。
现在问题是怎么找到一个\(0\)位数足够多的\(t\)。你发现随机一个数，期望就是有一半的\(0\)，但是如果我们运气太差就会死掉。
怎么办呢?我们随几对，每次求出一对的\(\operatorname{or}\)，找到\(\mathrm{popcnt}\)不超过一半的为止，然后随便选择其中一个就好了。这样运气就很难太差了。
然后你就发现这道题曾经收录于 CF思维题选㗅。还有两种做法我就不列举了。
505E : 竹子题!我超喜欢这个题的。
你谷中文题意很**离谱，我喜欢形象的原题面。说的是，你有一排竹子，你每天可以操作\(k\)次，每次选择一棵竹子砍掉\(p\)米，如果高度不足\(p\)米就砍成\(0\)，操作后每个竹子每天会长\(a_i\)米，求\(m\)天后最高的竹子最少可以是多高。\(n\leq 10^5,m\leq 5\times 10^3,k\leq 10\)。
二分答案。不过还是不好做/cy
时间倒流。问题变成，一开始所有竹子高度都是\(mid\)，每天所有竹子会先缩水\(a_i\)米，然后你每次操作可以把一棵竹子抻长\(p\)米，要求任意时刻每棵竹子的高度都不能变成负数。
所以我们可以算出来每棵竹子在不操作的情况下，接下来在哪一天变成负数，然后开一个堆，选取最早的进行操作就好了。
713D : 最大全\(1\)正方形是个经典dp，非常奇妙。
你考虑设\(dp(i,j)\)表示\((i,j)\)为右下角的最大全\(1\)正方形，那么对于一个\(1\)的格子\((i,j)\)，有转移 : \(dp(i,j)=min(dp(i-1,j-1)+1,dp(i,j-1),dp(i-1,j))\)。
然后考虑这个问题并不等价于矩形\(\max\)，因为你的最大正方形可能超出这个边界。
考虑答案的形式是\(\max_{i,j}(\min(i-x_1,j-y_1,dp(i,j)))\)，你发现这是最大化最小值，所以考虑二分。
二分之后我们就把\(i-x_1,j-y_1\)都干掉了!于是变成了\(\log\)次在线查询矩形\(\max\)。这个可以用二维st表搞定。
看起来我们可以通过把st表一维改成\(\log/\log\log\)为底，把复杂度砍到\(O(n^2+q\log n/\log\log n)\)。但是那样太难写了。
1039D : 好猛。
看到7s，想到这是cf，你就知道是根号\(\log\)或者\(\frac{5}{3}\)这样的东西了。
爆力怎么做?爆力是不是，草爆力怎么做?
看题解/ll
贪心。这个东西就是 赛道修建 啊!不过也不太一样，因为这里每个点只能被选一次，所以会更简单。考虑两个最长的儿子，我们要么把它们拼起来，要么就把其中更长的那个向上延伸，dp一下即可。
但是\(O(n)\)一遍还是太慢了。怎么办?
这里非常妙。根号分治，取阀值\(K=\Theta(\sqrt{n\log n})\)。小的部分直接爆力，复杂度是\(O(n\sqrt{n\log n})\)。
我们知道当\(k\geq K\)时答案不超过\(\frac{n}{K}\)，所以答案只有这么多种。并且因为答案单调，每一种答案是一个区间。可以对于每一种答案进行二分求出左右端点，这样复杂度是\(O(n\sqrt{n\log n})\)。
367E : 大力dp?
考虑 至少一个 很难受，我们还是转成 没有。
互不包含怎么做?这是经典结论。我们往上撒一些左右端点，保证从左往右扫过去，右端点不多于左端点，那么就有一种方案。
设\(dp(i,j,k)\)表示前\(i\)个点，撒了\(j,k\)个左，右端点。转移决策这个点是不选，选左端点，选右端点，都选；\(x\)处不能选左端点。
注意到\(n>m\)的话一定无解，所以\(n=O(\sqrt{nm})\)，这个dp复杂度是\(O(n^2m)\)的，也就是\(O(nm\sqrt{nm})\)。
存在奇妙\(O(nm)\)做法，参见这里。
827D : 似乎是简单题。
直接对于每条非树边找到它可以代替的最大的树边，树边找到覆盖它的边权最小的非树边即可。这个就是链取\(\min\)，可以用树剖+吉老师线段树完成，复杂度是三个\(\log\)。
草?这可不好。你发现数据结构学傻了，不用吉老师线段树啊，复杂度变成两个\(\log\)。
可以换成静态LCT，复杂度一个\(\log\)，不过没有必要。
671D : 似乎不是简单题。
简单想法是dp，不过我们需要处理覆盖到祖先的部分，所以复杂度就变成\(O(n^2)\)了。
呃具体是啥?设\(dp(u,i)\)表示覆盖了\(u\)子树内所有边和\(u\)到\(u\)深度为\(i\)的祖先链上所有边的最小代价，\(f(u)=dp(u,\mathrm{dep}(u)+1)\)也就是只需要覆盖到父亲的边，转移枚举覆盖上去的链是从\(u\)还是\(u\)的子树出发，剩下的懂的都懂。一开始预处理从\(u\)出发的方案，卷上一个儿子\(v\)的式子看起来是这样的 :
\[dp(u,i)=\min_{v\in\mathrm{ch}(u)}\left(dp(v,i)+\sum_{w\in\mathrm{ch}(u),w\neq v}f(w)\right)\]呃你发现一个很有意思的事情，就是后面那个\(\sum\)对于所有\(i\)都是一样的，所以我们可以枚举一个儿子\(v\)，把它的\(dp\)全局加上后面那个\(\sum\)的值，然后跟\(dp(u,...)\)取\(\min\)。现在问题变成 :
-
全局加
-
对应位置取\(\min\)
-
单点修改
发现第二个可以线段树合并，同时另两个操作产生的结点数是\(\log\)级别，所以总复杂度就是\(O(n\log n)\)，认为\(n,m\)同阶。
但是这题空间只有250m，导致线段树合并很容易就炸了……
换成平衡树启发式合并就好了。直接使用set会多个\(\log\)，不过没大问题。
存在奇妙可并堆做法，看起来就是不存这么多信息，转而直接维护方案。
你谷有人提供了线性规划对偶做法，可以直接转化成随便做问题，看起来好猛啊，不过谁会想这种东西（
1264D1/2 : 诶这个题APIO是不是讲过啊/jy
考虑如果没有?，这个东西等价于说我找一个尽可能长的子序列，让它前一半全是左括号，后一半全是右括号。那么我们可以枚举一个位置，维护左右各有多少左右括号，然后取一个\(\max\)。
你发现这是两个单调函数的\(\max\)，一个单减一个单增，所以\(\max\)一定是一段，这一段满足两边括号数量相同。进一步你发现每个位置上都至少有一个函数发生变化，所以\(\max\)只在一个位置取到，并且只有这个位置满足两边括号数量相同。
对于原题，我们枚举这个位置，计算两边各有多少方案搞出相同的括号数量，这个可以组合数选一选选出来，就做完了。
1270F : 8s?不禁想起前面的7s根号分治。
考虑如何形式地表示这个awesome。设前缀和是\(s\)，那么一个区间\([l,r]\)是awesome的，等价于\((s_r-s_{l-1})\mid(r-(l-1))\)。也就是说我们要算有多少对\((s_i-s_j)\mid(i-j)\)。
如果我们枚举一个\(d\)，求\((s_i-s_j)=d(i-j)\)，就可以拆开变成\(s_i-di=s_j-dj\)。现在是\(O(n^2)\)，然后呢?
对\(d\)根号分治!取阀值\(K=\Theta(\sqrt{n})\)
对于小的\(d\)，直接枚举\(d\)，然后爆力求出来每一种\(s_i-di\)的个数，从里面选两个贡献给答案。
对于大的\(d\)，你发现\(s_i-s_j\)很小，所以我们可以爆力枚举\(s_i-s_j\)，然后双指针扫一下这样的区间。假设我们枚举到左端点是\(i\)，右端点是在\([j_1,j_2]\)之间的，那么区间长度是在\([j_1-i+1,j_2-i+1]\)之间的，问题变成算一个区间中某个数倍数的个数，显然可以直接除一下做到\(O(1)\)。当然我们需要再减去\(d\)小的部分，也就是说在算之前需要把\(j_1\)跟\(T(s_i-s_j)\)取个\(\max\)。
总复杂度是\(O(n\sqrt{n})\)。
1019C : 这是一道神仙题。好像收录于 cf思维题选㗅?
再思考一遍吧。考虑我们不断加入一个点，看如果它没有被覆盖，那就选它，否则就不选它。
你发现这个东西在无向图上很成功，但是有向图就不行了，主要原因是可能出现\(u\rightarrow v\)但没有\(v\rightarrow u\)，这就会导致你先选\(v\)之后，选了\(u\)产生冲突。
那怎么修补一下?
你发现这个东西在无向图上太过成功了，以至于从集合中每个点出发，只需要走一步就可以到达所有点。考虑怎么根据这个来修补一下。
考虑还是不断加入一个点，如果它能被一步走到，那就不选它，否则就选它。
这个还是不对/ll，因为它能走到的点还是可能被选了但是走不到它。
核心问题就是，一个点能走到的点不一定可以回来走到这个点。考虑我们在加入这个点之前不加入它能走到的点，这就很好了!
于是我们就可以先不断删点，每次删掉一个点和所有它能走到的点，直到只剩下一个点，我们选择这个点，然后按照删掉的顺序倒着加入所有点。加入一个点和它能走到的点的时候，如果这个点可以被一步走到，那就不选它，否则选它。这样完全没问题。
757F : 草?
考虑先建出最短路DAG，那就是求哪个点在这个DAG上割掉之后，变的与\(s\)不连通的点最多了。
支配树!fuck。
你谷题解给出了一个不用支配树的做法，说的是考虑这个割掉之后不连通点的结构。如果一个点\(u\)只有一条入边，那么割掉这条入边连到的点，这个点\(u\)就没了。进一步，如果割掉某个点会使得\(u\)入边连到的所有点都没了，那么\(u\)也没了。
所以可以考虑拓扑排序，过程中把所有 割掉某个点会使得这些点全没了 的块缩起来。我们处理完\(u\)的入边连到的所有点之后，如果它们被缩成了一个点，那么把\(u\)也缩进去，否则就让\(u\)自己一块。最后答案就是最大的块大小。
注意对于\(s\)连到的点需要特判。
1344D : 这个式子看起来好离谱……
不过我们可以 求导!你发现它是上凸的，那么上凸函数的闵和还是上凸的，所以我们可以知道答案上凸，所以我们可以wqs二分一下，check就二分一下选多少最优就好了。
呃需要构造方案/jk，wqs二分据说现在有很可用的构造方法，但是我学不动/cy
不过这个题可以随便构造。我们二分出来选了得到变化量是\(0\)的那一段，大胆猜测这一段长度是\(\leq 2\)的，所以可以讨论一下得到方案。
535E : 一看就像是凸壳之类的?
简单想法是，你发现如果\(a\)在一项上比\(b\)强，那么我们只要使劲往那一项上堆就可以让\(a\)赢过\(b\)，所以不行的就是两项都弱的，排序单调栈就好了。
但是这个做法有问题，就是说可能同时存在两个人，分别在两项上比我们希望win的这个人强，那么我们可能就不能让这个人win了。
所以还是考虑凸壳。把每个人看成点\(\left(\frac{1}{a},\frac{1}{b}\right)\)，那么我们知道用时就是两项的距离和这个东西的点积，点积最小值在左下凸壳取到，所以我们求左下凸壳即可。
1458C : 这是数据结构题/jy
先考虑怎么表示IC操作，你发现如果把每一个位置看成\((i,j,a_{i,j})\)，那么I就是\((i,j,k)\rightarrow (i,k,j)\)，C就是\((i,j,k)\rightarrow (k,i,j)\)。这样我们就可以维护现在的每一维是原来的哪一维，然后维护每一维的shift就好了。
1149C : 好经典啊。
线段树可以利用括号序维护动态直径。
考虑类似于括号序莫队的，一条链的结构可以用一串左括号，一串右括号，或者一串右括号连着一串左括号描述。当然第三种包括前两种。
这样问题就变成了求所有区间消去匹配括号之后的最长长度，容易使用线段树维护。
具体地，我们先把左右括号变成\(\pm 1\)，然后你发现题目保证肯定匹配，问题变成找一个区间从中间断开，后面的和减去前面的和的最大值，做完了。
700E : 考虑先建立SAM。然后怎么描述，一个子串在另一个子串里出现至少两次?
你发现出现两次很麻烦，但是贪心地，我们找到随便两次出现，把前面后面无用的都删掉，这样就变成 前面出现一次，后面出现一次 了，也就是一个border。
然后就看起来可以描述了。你发现SAM的\(\mathrm{endpos}\)自动处理了 后面出现一次，一个点parent树上到根的链上所有点都满足这个，但是问题在于怎么处理 前面出现一次?
可以考虑把限制放宽回去，我们不要求它在前面出现是在最前面，只要求它除此之外还出现过就行了。
怎么描述 出现过?实际上可以通过\(\mathrm{endpos}\)很容易地解决这个问题，要看\(a\)是否在\(b\)中还出现一次，我们对于\(b\)找到随便一个\(\mathrm{endpos}\)记为\(p\)，那么如果在\([p-\mathrm{len}(b)+\mathrm{len}(a),p-1]\)中存在一个\(a\)的\(\mathrm{endpos}\)，那么\(a\)就在\(b\)中还出现一次了。
然后\(\mathrm{endpos}\)可以线段树合并出来，所以我们对于每个点倍增出来第一个在它里面出现至少两次的祖先，这一步是\(O(n\log^2 n)\)的，然后就可以可撤销化BiT/线段树维护一下到根的链，并直接转移了!
等等，还有一个问题，就是每个点可能有很多串，全转移一遍复杂度显然不能接受。不过大胆猜测我们只需要处理那个最长的或者最短的，然后你发现只处理最长的就过了。
呃真的有必要这么慢吗?
考虑双指针，但是你发现树上是不能双指针的。
但是你又发现这个结构可以做一些类似于双指针的事情，我们设\(dp(u)\)表示以\(u\)的最长串结尾的答案的话，那么对于一条祖孙链答案显然单调，并且由于我们的转移只有\(+1\)，计算\(dp(u)\)的时候只需要考虑最浅的和\(\mathrm{fa}(u)\)的\(dp\)值相同的结点，如果它转移不过来那就直接继承\(\mathrm{fa}(u)\)的\(dp\)值。这样就\(O(n\log n)\)了。
注意这里更多的是利用问题性质，而不是SAM性质，我并不知道这一性质是否可以推广到一些别的parent树上dp问题，不过我猜测不行。
605E : 哦这个题。
首先如果我们知道了所有点答案的大小关系，那么就可以对于每个点，从小到大尝试选择它的邻接点走过去。
然后你发现显然这个转移得到的答案一定是不优于那些比它小的点的答案的，所以我们可以尝试一个类似于Dij的做法。对于所有点动态维护它周围的点转移过来的结果，一开始只有\(t\)的答案是\(0\)，然后每次取出最小的来更新周围的点，随便精细实现一下就可以做到\(O(n)\)更新一次，总共就是\(O(n^2)\)。
351D : 你发现每个颜色至少需要一次，并且只要重排一次，把每个颜色排到一起，就可以每次干掉一个区间。所以问题变成是否存在一种颜色，出现位置构成等差数列，此外的部分就是简单的区间数颜色了。
然后就可以考虑莫队了!每个颜色开一个数据结构，支持插入/删除，然后看是不是等差数列。
呃众所周知等差数列有个经典hash。我们维护\(\min,\max\)，然后一些若干次的和就好了。砍堆的话回滚一下就好了。
呃实际上没有必要。你发现每次加入一定是加两边，所以可以直接维护一个双端队列。
呃实际上连hash也没有必要。我们既然都回滚了，不如直接开链表维护pre/suc，然后再开一个链表维护所有邻项差。这样写起来好像非常麻烦。
呃实际上链表也没有必要，因为我们处理的是下标，直接预处理出来就好了。
呃实际上连莫队也没有必要。
考虑我们求出\(f(i)\)表示如果\(i\)是它的颜色在区间中最后一次出现，左端点最左可以到哪里，还能使得这个颜色可以被一次操作干掉。
然后你发现，如果\(i\)到\(pre(i)\)和\(pre(i)\)到\(pre(pre(i))\)的区间长度是相同的，那么\(f(i)=f(pre(i))\)，否则\(f(i)=pre(pre(i))\)。
所以我们离线扫描线，问题变成区间加减，求全局有没有\(\geq 0\)的数，注意到所有数都是非负的，线段树维护一下就好了。
878C : 你发现一个人能赢，就是把每个人向她可能打败的人连边，从这个人出发可以到达所有人。
考虑这个图的形态，你发现两个人之间有至少一条边，所以这是一个比竞赛图要多的东西。缩SCC之后，入度为\(0\)的SCC都是可能胜出的人，而竞赛图缩完是一条链，所以只有一个这样的SCC。
问题变成动态维护SCC。考虑加入的时候尝试合并SCC，由于我们缩完之后的SCC之间都是可比的，我们可以二分找到第一个和最后一个跟新点可比的，这样把中间缩成一个就好了，可以用set维护，实际上也可以直接用set找不可比的SCC。复杂度\(O(nk\log n)\)。
765F : 过于经典了……
1209F : 这个字典序就很离谱。
首先考虑位数没啥用，因为我们可以把每条边拆开成最多六条边，这样只需要考虑一位的情况了。
然后咋做?首先我们肯定是找最短的，此外我们要找字典序最小的，那就直接bfs一遍，然后在最短路DAG上爬就好了。
呃等等，你发现这个我们爬不动……
不过没有关系，我们可以直接魔改bfs。先走0，再走1，…，最后走9这样的即可。复杂度\(O(n\log n)\)，其中\(\log\)是因为拆边。
338D : 看起来说的是，你要在一个巨大的\(\gcd\)矩阵里面找一行的一段为\(a\)。
呃毫无头绪。
这个数据范围好奇怪啊，1e12 1e4的，看起来……呃好像看不出什么来，毕竟什么小常数2/3怎么想都不是1s吧……
完全不会/ll
考虑\(\gcd(a,b)=c\)，等价于\(\gcd(\frac{a}{c},\frac{b}{c})=1\)，这就非常好。然后我们就得到一车\(\gcd(\frac{i}{a_p},\frac{j+p-1}{a_p})=1\)这样的方程。
然后你发现看起来这个整除的限制已经非常强了，我们可以先得到一堆同余方程，然后exCRT得到一个通解，这个东西形如\(i\equiv 0\pmod{l},j\equiv t\pmod{l}\)，其中\(l\)是\(a\)的\(\mathrm{lcm}\)。
然后考虑这么一件事 : 如果有解，那么取\(i=l\)一定可行。
为什么?考虑\(i\)的因子越少，越容易让那个\(\gcd=1\)的方程成立。
然后我们考虑\(j\)，你发现用Euclid来做\(\gcd\)的时候，第一轮就可以把加上的那些\(l\)全膜掉，所以我们也只需要检查最小的\(j\)。做完了。
1389F : 好眼熟。
考虑dp，按右端点排序，设\(dp(i)\)表示只考虑前\(i\)条线段，强制选第\(i\)条线段的答案。转移的时候分颜色建两棵线段树维护就好了。
另一种做法是模拟网络流，考虑每条线段建一个点，冲突就连边，然后就变成最大点独立集，转成最大匹配就好了。
然后咋做?按照右端点排序，依次从左部点出发增广，为了尽可能减少后效性找到右端点最左的进行匹配。可以使用multiset做这件事，就做完了。
1368F : 比较要命的事情是，Alice先操作，所以Bob在最后一定会有一次操作。
考虑我们只需要保持没有连续\(k\)个亮着的灯，那么Bob就输麻了，而当亮着的灯数量达到\(n-\lceil\frac{n}{k}\rceil\)的时候，Alice就输麻了。
所以我们猜测答案就是\(n-\lceil\frac{n}{k}\rceil-k+1\)，因为Bob还要操作一次。构造方案也很简单，只需要一开始处理好哪些位置要点亮，然后看到没点亮的就点上就好了。
呃那么\(k\)显然是取根号附近的一个数最优，所以我们就枚举几个试一试就好了。
1437F : 排序肯定不亏。
然后爆力怎么做?设\(dp(i,j)\)表示考虑前\(i\)个人，强制放\(i\)，已经放了\(j\)个的方案数。转移的时候就枚举下一个是谁就好了。
如何优化?
你发现对于每个\(i\)，不管\(j\)是什么，可以放的人都是固定的。假设有分别\(x,y\)个人，放进来会happy/sad(这显然分别是没选的里面的一个后/前缀)，那么我们可以考虑怎么从这里面选一个happy的或者选一个sad的。
-
放一个happy的 : \(dp(k,j+1):=dp(k,j+1)+dp(i,j)\)，其中\(k\)是我们要放的那个
-
放一个sad的 : \(dp(i,j+1):=dp(i,j+1)+y\cdot dp(i,j)\)
呃你发现第二个转移容易处理，但是第一个还是需要枚举\(k\)。
考虑转移的结构，你发现我们每次都是转移到一个后缀，所以可以先打个标记，然后边dp边前缀和就好了。
还有一个\(O(n\log n)\)，瓶颈在排序的做法。
还是排序。
考虑这个排列的结构，我们的前缀最大值只会在一个happy的人处改变，所以可以把这个排列按照happy的人分成若干段。每一段内部全是sad的人，那么我们可以考虑处理到一个happy的人的时候把这些sad的人全加进去，也就是尽可能多地选人，转移的时候可以用组合数来选出位置。
考虑设\(dp(i)\)表示只考虑前\(i\)个人，\(i\)是最后一个happy的人的序列个数，这里不要求把前\(i\)个人选完，并且这是长度为\(n\)、有一些位置没填的序列。
设\(g(i)\)是\(i\)前面最后一个因为\(i\)感到sad的人。如果我们尽可能多选人的话，显然\(dp(i)\)的序列长度就是\(g(i)+1\)。
然后考虑怎么转移，我们枚举上一个happy的人\(j\)，那么就先放进去\(dp(j)\)，然后放一个\(i\)，然后尝试把\(g(i)-g(j)-1\)个人胡乱放。
放一个\(i\)很简单，她必须放在第一个非\(0\)的位置，因为后面的东西都不能放在这个位置了。
这\(g(i)-g(j)-1\)个人，她们必须放在\(i\)后面，你发现\(i\)后面现在有\(n-g(j)-2\)个空位，那么就有\(\binom{n-g(j)-2}{g(i)-g(j)-1}\)种方案选出来，再排列一下还需要乘上\((g(i)-g(j)-1)!\)。所以式子就是 :
\[dp(i)=\sum_{j=0}^g(i)\binom{n-g(j)-2}{g(i)-g(j)-1}(g(i)-g(j)-1)!dp(j)\]优化也很简单，你发现那个系数拆开就是
\[\frac{(n-g(j)-2)!}{(n-g(i)-1)!}\]然后上下是独立的，所以把下面移到左边，就前缀和优化了。
1394C : 考虑显然只跟里面NB的个数有关，跟具体是什么没有关系。
把NB的数量画到平面上，然后二分答案，每个\(s\)就确定了一个很奇怪的形状，这个东西是凸的所以可以表示成半平面交，然后把它们都交起来看是不是空的就好了。
注意到一共只有六种方向的半平面，所以我们可以直接对于每一种取一个交，这个太简单了。然后看是不是空的话，判三组对面的半平面交都不为空就好了。
构造方案?我们随便在四个横平竖直的半平面上枚举一个点，看它是不是满足剩下两个半平面的限制就好了。
1111D : 1e5的话应该比较阳间吧（
呃考虑串这么长，实际上只有每个字母出现次数是有用的。
呃考虑询问这么多，实际上只有\(\Sigma^2\)种是不同的(如果你觉得问同色也算问，那就加个\(1\)好了)。如果对于每一类跑一遍\(O(n)\)，那么算量就是2e8，完全不慌。
考虑主要问题是分在同一边这件事，我们需要背包背出来，每次查询就是合并两个物品，注意背包的时候还要组合数一下，但是这么一搞复杂度变成\(O(n\Sigma^3)\)了/dk，是不是卡卡常就过了啊/jy
如何优化?慢就慢在，我们每次都要重新跑一遍。
仔细想想你发现这个东西跟 消失之物 有点像。
还记得那个题的\(O(nm)\)做法吗?
这个背包也可以写成多项式卷积，所以我们可以考虑加入一个物品的逆操作，也就是删除一个物品，它对应多项式除，枚举几种写法就可以找到一个对的。
这个有啥用?考虑我们可以先把所有字母加进去，然后依次删掉每两个字母，加入它们的合并，得到答案再删除它们的合并，加入它们。每次删是\(O(n)\)的，所以就\(O(n\Sigma^2)\)了。
585E : 5s看起来就很可疑/fad
这个翻译是瞎扯/fad
它说的是，商店里有很多邮票，有一个人要去买一张邮票，商店会再送给她剩下的一些邮票，如果买的和送的邮票的面值\(\gcd=1\)，但是送的\(\gcd>1\)，就是好的，求有多少方案是好的。
呃小朋友想一想，你发现这个面值少的可怜只有1e7，这是为什么?
gcd卷积。考虑我们先把所有数卷起来得到一个 \(\gcd=i\)的方案数 的序列，然后剔除掉\(\gcd=1\)的方案数，然后再卷上所有数(这里每一位是\(i\)的个数)，取\(\gcd=1\)的就是答案。
现在问题是怎么把所有数卷起来。考虑类似于某个经典题的做法，一个数自己法嘛塔一下乘进去，就相当于给因数全都乘上\(2\)，所以打一个标记，然后用法嘛塔来推这个标记，然后再逆法嘛塔回去。这就做完了，复杂度\(O(n+v\log\log v)\)。
另外题解里看到喷585F的，不得不说确实不难，就直接把所有够长的子串拿出来爆力建ACAM，然后在ACAM上数位dp就好了。
gcd卷积
啊你说怎么\(O(v\log\log v)\)做gcd卷积?
考虑整数就是多重集，and卷积的时候我们用法嘛塔(子集后缀和)，这里我们也可以用法嘛塔(狄利克雷后缀和)。我感觉广义的莫比乌斯变换应该就是，偏序集上的前/后缀和吧，所以这么说好像完全没问题。
先考虑前缀和怎么做。
枚举每一维(每个质数)，然后处理贡献就好了。维数很多，是\(O(\frac{n}{\log n})\)的，但是你发现每个数只在很少的维度上非\(0\)，而是\(0\)的话就不会有任何贡献，也就是说我们只需要处理枚举到这个质数的倍数，复杂度是\(O(n\log\log n)\)。
那么后缀和怎么做?把转移反过来就好了。
逆呢?反过来写就好了。
1091F : 怎么看怎么像智障题/ll
但是我和苏铁想了半天不会做/kk
时间倒流，问题变成一开始没有能量(因为一定是飞完了最优)，飞增加能量，走或者游减少能量。
贪心地，我们一定是希望把两段后缀的草和水都飞过去。
考虑这个东西怎么想都很单峰，所以我们可以二分一个，然后贪心地选另一个，目标是。复杂度\(O(n\log v)\)。
看起来你谷题解给的是反悔贪心。先在最前面积累足够的能量，让后面一直飞。然后一边模拟一边尝试进行替换，把一些走换成游，做完了。
482C : Game with Stingers
你发现串长只有\(20\)，这个看起来就很可疑。
简单想法是枚举问了哪个串，然后开一个队列爆力扩展出所有可能问到的状态。这样做是\(O(2^mnm)\)这样的，完全过不了。
要想优化，考虑抛开这个枚举串。计算\(c(S)\)表示问了集合\(S\)之后还有多少串不能区分，\(dp(S)\)表示问了\(S\)的话，期望还需要问多少步。
\(dp\)的转移容易做到\(O(2^mm)\)，但是\(c\)怎么算?
考虑我们枚举每一对串，看它们有哪些位置是相同的，如果我们问到的集合是这个相同的位置的子集，那么我们就没法区分这两个串。所以可以把每一对的这个东西挂到一个数组上，然后做子集后缀和，就可以搞定\(c\)了!
1254D : 首先这个期望显然是假的。我们枚举所有情况做一遍，最后输出乘上\(\frac{1}{n}\)就好了。
现在问题变成，修改是以每个点作为根给\(v\)子树加。
你发现以\(v\)为根每个儿子的子树做出的操作是相同的，都是对\(v\)剩下儿子的子树加。所以我们可以枚举一棵子树往其它子树上打标记。
但是这太慢了。考虑根号分治?
对于小点，我们直接爆力。对于大点，我们往大点打上标记，查询的时候枚举所有大点计算贡献。
小点爆力可以用\(O(1)-O(\sqrt{n})\)的区间加单点查询维护dfs序，大点可以用st表lca做到每个\(O(1)\)。复杂度\(O(n\sqrt{n})\)。
也有奇妙树剖做法。考虑差分一下然后树剖，我们修改的时候只改父亲和重儿子，查询的时候在轻儿子处爆力。用BiT维护，复杂度是俩\(\log\)。
呼~做完一页了~
好像致远星了，现在已经不是一页了（
不过没关系。
487D : 你发现列数很少。
这种题经典想法就是用线段树维护。
考虑每个区间维护从两侧走进来的点分别会到哪里去，然后就可以合并了，然后就做完了。精细实现的话这里是\(m\)而不是\(m^2\)。
呃你说怎么求答案?就比如这个位置是>，那尝试在后面走出去，如果走回来了再到前面去，这样走最多\(m\)次就报告死循环即可。
1372E : 当你同时看到dp和greedy的时候，你就知道这题不可做/fad
考虑一件事情，因为是平方，我们很可能希望一选就尽可能多选，否则就不选。
考虑我们枚举一列让它尽可能多选，然后递归还没有1的部分，然后你就看到了一个区间dp。
设\(dp(l,r)\)表示只考虑所有左右端点都在\([l,r]\)内的段的答案，转移就枚举一列，用这些段尽可能多地往上填1。精细实现的话复杂度是\(O(n^3)\)。
然后就可以证明正确性了，调整法很容易就证完了。注意直接根据这个思路做贪心是错误的。
1503D :
有一个来自cf用户 TheScrasse 的想法。妈呀他的头像好棒啊（
翻和不翻很奇怪，我们先全翻成\(a<b\)，然后重新赋予每张牌翻的代价，也就是说有的牌翻的代价变成\(1\)，有的是\(-1\)。
考虑把所有牌看成一条线段\([a,b]\)，那么问题变得很直观了。
如果两条线段没有交，那么不管怎么翻都无解了。这说明任何一条线段都是由一个\(\leq n\)和一个\(>n\)的数组成的，也就是说它们一定都跨过中点。
如果两条线段相交而不包含，那么它们翻的情况是不同的。比如两张牌1,3和2,4，如果取了1,3，一定得取4,2；如果取了3,1，一定得取2,4。以下如果不特殊说明，默认 相交 指的是 相交而不包含。
如果两条线段包含，那么它俩可以随意。
看起来这很充要，但是我们可以干什么呢?
204E : 直接广义SAM?
但是要对每个串求，那就对于每个子串贡献到它的所有终止结点，这是一个子树加，可以差分-前缀和搞定。
快NOI了我还不会写广义SAM/jk
618F : 这个题太过经典了。
考虑鸽子原理，但是仔细想想考虑不出来。
我们大力放弃性质。先只考虑两个子集大小相同，此时就可以建立一个对应，然后就变成\(a_i-b_i\)加起来是\(0\)了。
然后继续放弃性质，我们只考虑区间，这样就可以拆成前缀和了。原因是，你发现如果我们把前缀和的值域全都限制在\([0,n-1]\)内，那么一共有\(n+1\)个前缀和，就可以套用鸽子原理找到相等的一对了。
考虑\(a,b\)的前缀和，记为\(S(a),S(b)\)，你发现如果\(a\)的总和不小于\(b\)，那么对于每个\(i\)，都存在\(j\)满足\(S(a)_i\geq S(b)_j\)。由于每一项都是\([0,n-1]\)内的，我们可以找到\(0\leq S(a)_i-S(b)_j\leq n-1\)，可以用双指针扫出来。这样我们得到\(n+1\)个\([0,n-1]\)内的值，就鸽子原理即可。
960G : 呃你发现排列就是大小关系，排列和笛卡尔树形态建立了双射。
考虑前缀最大值就是在大根笛卡尔树左链上的，后缀最大值就是右链上的，然后问题变成左右链长度分别是\(a,b\)的\(n\)个点的二叉树有多少。所以把一堆二叉树卷起来就行了。
然后我好像完全错了。想了想我发现排列和笛卡尔树并没有双射，直观上来看就是二叉树比排列少。太好笑了（
所以我们需要一些别的想法。你发现我们以全局最大值分成两部分，左边有前缀最大值，右边有后缀最大值。所以我们要做的就是把左右卷起来。
考虑左边是什么。容易想到dp，设\(dp(i,j)\)表示长\(i\)的排列，有\(j\)个位置是前缀最大值的方案数。转移考虑插入最小的数，那么它只有插在第一位才能成为前缀最大值，而它插在哪都不会影响别的前缀最大值。
后缀最大值显然是对称的。
然后我们就不是很会优化了，因为这个dp是\(n^2\)的。写出式子来看看?
\[dp(i,j)=(i-1)\cdot dp(i-1,j)+dp(i-1,j-1)\]你发现它很像斯特林数，事实上它就是第一类斯特林数，套用快速求一行/一列斯特林数的做法即可。
961G : 推式子题。
我们计算每个数的贡献，容易知道答案就是
\[\sum_{i=1}^n w_i\sum_{j=1}^n j\binom{n-1}{j-1}{n-j\brace k-1}\]。然后我们就开始推式子了。你可能已经知道这是什么题了/jy
然后你发现如果工业基础足够，根本不用推式子，毕竟这是cf。考虑我们直接预处理后面那个东西，因为它和\(i\)并没有关系。
这个东西就是\(i\binom{n-1}{i-1}\)和\({n-i\brace k-1}\)的卷积的\(n\)次项。使用求一列斯特林数的科技即可。
然而膜数居然是1e9+7/jy，那就三膜呐塔塔硬上/se
题解区看到了简单的推式子方法，使用生成函数。
考虑shift比较恶心，并且斯特林数和EGF比较搭，这个组合数可以变成二项卷积，所以我们设\(t=k-1\)，把后面那个东西改写成
\[\frac{1}{n}\sum_{j=1}^n \binom{n}{j}j^2{n-j\brace t}\]。\(j^2\)就是\((z^2+z)e^z\)，\(\binom{n}{j}\)已经没了，\({n-j\brace t}\)据说是\(\frac{(e^z-1)^t}{t!}\)，于是答案就是
\[\frac{1}{n\cdot n!}[z^n]\frac{(z^2+z)e^z(e^z-1)^t}{t!}\]。只考虑后半部分，然后开始推吧（
\[\begin{aligned} &[z^n]\frac{(z^2+z)e^z(e^z-1)^{k-1}}{(k-1)!}\\ =&[z^n](z^2+z)\frac{(e^z-1+1)(e^z-1)^{k-1}}{(k-1)!}\\ =&[z^n](z^2+z)\frac{(e^z-1)^k+(e^z-1)^{k-1}}{(k-1)!}\\ =&[z^n](z^2+z)\left(k\frac{(e^z-1)^k}{k!}+\frac{(e^z-1)^{k-1}}{(k-1)!}\right)\\ =&[z^n](z^2+z)\left(k\frac{(e^z-1)^k}{k!}+\frac{(e^z-1)^{k-1}}{(k-1)!}\right) \end{aligned}\]局势已经十分明朗了!后面那个东西是\(k{n\brace k}\)和\({n\brace k-1}\)，前面是两个shift。完全展开并放上之前砍去的东西，答案就是
\[k{n-2\brace k}+k{n-1\brace k}+n{n-2\brace k-1}+n{n-1\brace k-1}\]，当然这个式子还可以继续化简。然后就变成求一些斯特林数了，看起来可以\(O(n)\)搞定。
442D : 直接做就是重链剖分，但是试一试你发现wa了。不过我们至少知道答案是\(\log\)级别的。
容易想到一个dp。因为是给边染色，我们设\(dp(u)\)表示染完\(u\)子树和\(u\)的父边的答案。转移就是在子树里选最大的把它连过来，剩下的只好\(+1\)，所以我们只需要用到最大值和次大值。
然后就简简单单!因为答案是\(\log\)级别的，我们可以爆力更新到不能继续更新，用每个点\(dp\)值的增加摊掉爆力的复杂度，总共是\(O(n\log n)\)。
356D : 是不是收录过啊（
你发现如果没有这个\(s\)，这就是智障题。
然后你发现点权和这个事情就是所有根的\(a\)之和，所以我们背包背出根即可，当然要求最大的是根之一。
但是数据范围很大/ll，不过你发现可以bitset，然后就做完了。
338E : 如果我们只判定一次，显然是分别正着、倒着排序，然后直接check一遍就好了。
然后容易想到数据结构维护这个区间，但是判定起来总是有点麻烦，因为你需要处理shift。
然后你发现我们可以这么解释这个事情，对于每个\(a_i\)处理一个它的可行后缀\(f_i\)，然后按照这个后缀长度从小到大选。
然后你发现这么一搞就简单多了，因为我们只需要看\(f_i-\mathrm{rank}(i)\)是不是负的就好了，平衡树维护\(\min\)即可。
724G : 好眼熟（