破防场。全是诈骗提。
但是很有可以学的东西！
\(I.\)
给定 \(n\) 个 01? 串，? 可以替换为 0 或 1。称替换完的串集合为该串的生成串。
问所有 \(n\) 个串的生成串集合的并的大小。
长度不同的串分开处理。
对于长度 \(\le 20\) 的串，暴力枚举生成串，map 去重。
对于长度 \(> 20\) 的串，串个数 \(\le 20\)，暴力枚举子集进行容斥。
这是根号分治！
这个故事告诉我们，根号分治完以后下半部分努力向尽量简单的方向走！不要想复杂！
\(L.\)
字符串 \(s\)，修改单个字符或询问 \(border\) 长度和 \(s\) 在 \(t\) 中出现次数的乘积，强制在线。
诈骗。\(|s|>|t|\) 时出现次数为 0，答案为 0； \(|s|\le |t|\) 时暴力 \(KMP\)，复杂度 \(O(\sum|t|)\)。
这是签到题！
这个故事告诉我们，不要相信别人的翻译，仔细读题！
\(E.\)
无向图。动态加边删边修改点权，询问一个点邻居 + 自己的点权和。
很厉害！
给边定向，无向图上度数小的点向大的连有向边。可证出度最大值 \(O(\sqrt{m})\) （\(m\) 是边数）。
记 \(val_u\) 为连向 \(u\) 的入边的起点的点权和。
加边时更新边出现次数，从无到有时更新 \(val\)。
删边时更新边出现次数，从有到无时更新 \(val\)。
为了维护上面那个东西，可以 \(O(\sqrt{m})\) 次修改重构一次有向图，重构复杂度 \(O(m\sqrt m)\)。（但是题解不是这么干的？）
修改点权时修改出边的 \(val\)，复杂度 \(O(\sqrt m)\)。
询问时答案为 \(val_u\) 加上所有出边的点权，再加上自身点权。
总复杂度 \(O(q\sqrt m+m\sqrt m)\)。
感觉是个很厉害的 trick！
标签：le,20,val,厉害,多校,sqrt,牛客,复杂度,点权 From： https://www.cnblogs.com/jimmywang/p/17612586.html