8.22 万灵药（SAM + Trie + 树剖 + 线段树）
8.22 万灵药（SAM + Trie + 树剖 + 线段树）
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141438811
http://cplusoj.com/d/senior/p/479?tid=66c55d60c098fe0f6786d470
考虑如何求两个前缀的最长后缀
我们建一个SAM，把这两个前缀找出来，他们的公共后缀集合为这两个点在fail树上的公共祖先
那么最长后缀就是它们lca对应的最长串
接下来我们要统计这些串的前缀，首先肯定要拿一个trie来维护
直接建trie是 的，但是这里有一个重要的性质，就是我们发现SAM节点和trie树节点是一一对应的
具体的，当前SAM节点在trie树上的父亲必然是某个走到当前节点的节点。我们只需要判断符合条件的len就行
因此我们现在把trie建出来了
我们现在要实现的功能是什么？
对于trie树，我们要查询一个点到根路径上所有值的权值，并对这条路径所有点的权值±1
这个东西直接剖就行
后面维护理论上要拿zkw或者树状数组才行，但我线段树冲过去了，复杂度是双log的
如果改成全局平衡二叉树，那就可以优化成单log了，黄队好像打了
my code：
1 |
|
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-30
贪心找性质+DP表示+矩阵表示+线段树维护：CF573D
贪心找性质+dp表示+矩阵表示+线段树维护：CF573D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133437456 比较套路的题目 首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况： 我们发现第3个人没了，所以可以出现跨2的情况 然后直接上dp，由 i−1,i−2,i−3i-1,i-2,i-3i−1,i−2,i−3 转移过来。 然后这显然可以拿矩阵表示。 然后显然可以拿线段树维护。 后面三部分都是比较套路...
2023-09-26
（非颜色、包含）线段类问题——离线+扫描线+DS：0926T4
（非颜色、包含）线段类问题——离线+扫描线+DS：0926T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133309861 这种类型的题其实很单一 首先有一堆线段，有询问，直接离线，然后上扫描线，然后套DS 问题来了，ds维护什么？ 此题询问的看似是单点问题，本质是区间问题。 我们要尝试对题目进行转换，如果整个区间所有都满足，则单点必然满足 回到此题。首先扫描线满足了右端点。 那么ds只能维护左端点了。 既然是维护端点值，那么只能维护最值。 维护最值...
2023-10-05
长剖与贪心+树上反悔贪心：1004T4
长剖与贪心+树上反悔贪心：1004T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133575747 长剖的本质是一种贪心。（启发式合并本质也是类似哈夫曼树的过程） 在此题中，首先肯定变直径，然后选端点为根。然后选叶子。而每个叶子为了不重复计算，可以只计算其长剖后所在链的贡献。（本题精髓，用长剖来贪心） 然后钦定某个点必选，就是一种反悔贪心。很显然的思路是删掉排名 2∗k−12*k-12∗k−1 的叶子，但考虑： 所以需要考虑离其最近被选的点 1234...
2023-10-18
set维护连续段+线段树：1018T2
set维护连续段+线段树：1018T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133914164 http://cplusoj.com/d/senior/p/386?tid=652f5fe6c1fe41bc229c18fb 线段树维护01，和，支持翻转操作 用类似珂朵莉树的方法维护连续段，连续段之间分别统计，取max 1234567891011121314151617181920212223242526272829303132333435363738...
2023-10-10
注意分类讨论完整性：CF1371F
注意分类讨论完整性：CF1371F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133745577 https://www.luogu.com.cn/problem/CF1371F 此题要分类讨论完全 容易漏掉 >>>>><<<<< 在左右或中间的情况 多对拍 123456789101112131415161718192021222324252627282930313233343536373839...
2022-04-29
【CF339D Xenia and Bit Operations】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16207447.html 题目链接 题目 Xenia the beginner programmer has a sequence $ a $ , consisting of $ 2^{n} $ non-negative integers: $ a_{1},a_{2},…,a_{2^{n}} $ . Xenia is currently studying bit operations. To better understand how they ...