Table of Contents
Merge 操作是可持久化结构里的一个常见操作（在 Fhq-Treap 里、甚至是最基本的操作！），
而线段树又以其灵活的懒标记系统，绝对是算法竞赛里最最灵活，最最实用的数据结构，个人认为，能否灵活的使用线段树是区分「菜鸡」和「大牛」的最好 Critiria 。。。
一旦掌握「线段树合并」这一进阶搞法，就又可以无脑的解决一系列树上统计问题、优化树形 DP 的转移等等，而且时间复杂度通常比替代算法更优！
优势：泛用性强，在线算法，时间复杂度优秀
劣势：烧内存，偶尔需要使用一些技巧优化空间
主席原版文献里的母题，这个题里使用线段树合并的优势就非常明显了。。。
https://www.luogu.com.cn/record/57421680
https://codeforces.com/contest/600/submission/127804505
先来个热身，这个题记得 当年 只会动态树，于是比赛时在怒秀动态树，然后被卡到比赛结束。。。
赛后看了一下 shi 哥树上差分轻松 dfs 的做法，恍然大悟，所以印象深刻。。。
当然其实动态树秀成功了就没任何问题好吧！
不过最好的做法绝对还是树上差分 + dfs()。
131 C 那个题等于这个题 z always = 1 弱化。。。
所以还是可以做树上差分。。。
只有需要用支持求最大值的数据结构维护。。
平衡树启发式合并、线段树合并什么的显然都行。
和上题差不多，不过这次是求前缀和，然后这玩意是可加的。
于是直接一颗树状数组就结束了。
我们不仅能够使用数据结构优化转移函数，还可以使用数据结构进行整体转移。。。
在掌握了线段树合并之后，一般这类题目写出暴力 DP 算法就已经成功 90% 了。。。
这个题实在是有点优雅。。。。。题意足够的简单。。做法也足够的高级。。
这个时候之前那种拆成两个 insert 的写法就有巨大优势了。。。因为这个题插入的区间都是覆盖整个数轴的。。所以外层的 insert 直接可以删掉了。。。
https://codeforces.com/contest/932/submission/127774764
我卡了好久，感觉非常难，状态转移类似 cdq 分治。
首先得先会做这个线性版本。
https://codeforces.com/problemset/problem/1327/F
然后我们考虑树 dp，加维，记录往上可以被豁免的位置（最近的染色边）。
然后就可以先 36 分的 O(n2) 暴力了。
最后上线段树合并优化即可。
虚树、树上差分、线段树合并
https://www.luogu.com.cn/problem/P5327
不错的主席树维护虚树的问题。
后缀自动机、线段树合并
https://codeforces.com/contest/700/submission/128074499
后缀自动机、线段树合并
https://blunt-axe.github.io/2019/12/07/20191207-NOI2018-Name/
先不考虑 [l, r] 。。。
那么基本就是 SAM 求 LCS 的方法，得到 T 串的每个前缀在 S 串中能被识别的最长后缀，记做 lcs[]。
有了这个就可以方便的排出掉不满足答案的子串了。
其实已经做的差不多了。。。考虑 [l, r]，那么就是在求 lcs[] 的过程不能单纯看目标状态存在不存在，而需要去看目标状态的 endpos 集合。
可以使用线段树合并，具体复制一下上题的代码即可。
https://www.luogu.com.cn/record/57612290
void _get_lcs(char s[], int n) {
int l, r; RD(l, r); --l, --r;
int u = 0, ll = 0;
REP(i, n) {
while (u && !v) u = p, ll = len[u];
if (v) ++ll, u = v;
lcs[i] = ll;
}
}
#define vv (v && (a = l+ll, b = r, Query(rt[v])))
void get_lcs(char s[], int n) {
int l, r; RD(l, r); --l, --r;
int u = 0, ll = 0;
REP(i, n) {
while (u && !vv) if (--ll == len[p]) u = p;
if (vv) ++ll, u = v;
lcs[i] = ll;
}
}
#undef vv
下面这个还是非常容易写错的。。比如 这里。
枚举模式串 P 的每一位，计算文本串 T 中有多少个位置曾经匹配到这个位置。这个只要计算当前状态的 endpos 集合大小即可。
对于匹配成功的情况，还要过滤掉所有成功位置之后的 endpos，因此需要上线段树合并。
https://darkbzoj.tk/submission/150716
广义后缀自动机、线段树合并
https://codeforces.com/problemset/problem/666/E
应该可以 SAM + 线段树合并的吧。。。
https://uoj.ac/contest/62/problem/608
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。