传送门

• HJT，线段树合并，不为人知的实用技巧
• 题单，线段树合并：从入门到精通

Merge 操作是可持久化结构里的一个常见操作（在 Fhq-Treap 里、甚至是最基本的操作！），
而线段树又以其灵活的懒标记系统，绝对是算法竞赛里最最灵活，最最实用的数据结构，个人认为，能否灵活的使用线段树是区分「菜鸡」和「大牛」的最好 Critiria 。。。
一旦掌握「线段树合并」这一进阶搞法，就又可以无脑的解决一系列树上统计问题、优化树形 DP 的转移等等，而且时间复杂度通常比替代算法更优！

优势：泛用性强，在线算法，时间复杂度优秀
劣势：烧内存，偶尔需要使用一些技巧优化空间

模板题

[POI2011]ROT-Tree Rotations

主席原版文献里的母题，这个题里使用线段树合并的优势就非常明显了。。。
https://www.luogu.com.cn/record/57421680

CF600E Lomsat gelral

https://codeforces.com/contest/600/submission/127804505

CodeForces #121 C. Fools and Roads

先来个热身，这个题记得 当年 只会动态树，于是比赛时在怒秀动态树，然后被卡到比赛结束。。。
赛后看了一下 shi 哥树上差分轻松 dfs 的做法，恍然大悟，所以印象深刻。。。

当然其实动态树秀成功了就没任何问题好吧！
不过最好的做法绝对还是树上差分 + dfs()。

[Vani有约会]雨天的尾巴 /【模板】线段树合并

131 C 那个题等于这个题 z always = 1 弱化。。。
所以还是可以做树上差分。。。

只有需要用支持求最大值的数据结构维护。。
平衡树启发式合并、线段树合并什么的显然都行。

P3605 [USACO17JAN]Promotion Counting P

和上题差不多，不过这次是求前缀和，然后这玩意是可加的。
于是直接一颗树状数组就结束了。

优化树形 DP

我们不仅能够使用数据结构优化转移函数，还可以使用数据结构进行整体转移。。。
在掌握了线段树合并之后，一般这类题目写出暴力 DP 算法就已经成功 90% 了。。。

Codeforces Round #463 F. Escape Through Leaf (李超线段树合并)

• https://www.cnblogs.com/zjp-shadow/p/9180474.html

这个题实在是有点优雅。。。。。题意足够的简单。。做法也足够的高级。。
这个时候之前那种拆成两个 insert 的写法就有巨大优势了。。。因为这个题插入的区间都是覆盖整个数轴的。。所以外层的 insert 直接可以删掉了。。。

https://codeforces.com/contest/932/submission/127774764

[PKUWC2018]Minimax

我卡了好久，感觉非常难，状态转移类似 cdq 分治。

NOI 2020 命运

首先得先会做这个线性版本。
https://codeforces.com/problemset/problem/1327/F

然后我们考虑树 dp，加维，记录往上可以被豁免的位置（最近的染色边）。
然后就可以先 36 分的 O(n2) 暴力了。

最后上线段树合并优化即可。

结合虚树

[ZJOI2019]语言

虚树、树上差分、线段树合并
https://www.luogu.com.cn/problem/P5327
不错的主席树维护虚树的问题。

结合后缀自动机

Codeforces Round #364 E. Cool Slogans

后缀自动机、线段树合并
https://codeforces.com/contest/700/submission/128074499

「NOI 2018」你的名字

后缀自动机、线段树合并
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

下面这个还是非常容易写错的。。比如 这里。

BZOJ 3413. 匹配

枚举模式串 P 的每一位，计算文本串 T 中有多少个位置曾经匹配到这个位置。这个只要计算当前状态的 endpos 集合大小即可。
对于匹配成功的情况，还要过滤掉所有成功位置之后的 endpos，因此需要上线段树合并。

https://darkbzoj.tk/submission/150716

Codeforces Round #349 E. Forensic Examination

广义后缀自动机、线段树合并
https://codeforces.com/problemset/problem/666/E

UOJ 608 机器蚤分组

应该可以 SAM + 线段树合并的吧。。。
https://uoj.ac/contest/62/problem/608

Posted by xiaodao
Category: 日常