树同构

Prufer 序列

拓展域并查集

可持久化数据结构 3

线段树分治

最小割

一般图最大匹配

洛谷p4585

线段树，分治，可持久化，字典树

有 $n$ 个商店，编号为 $1\sim n$。每个商店有一个价格为 $v_i$ 的特殊商品。接下来 $m$ 个操作：

1. 时间流逝一个单位，同时商店 $s$ 额外进货一种价格为 $v$ 的商品
2. 给定 $l,r,d,x$ 表示一个顾客的信息，询问该顾客的最大满意度。(满意度等于 $x$ 异或顾客可以购买的商品价格)

记询问时刻为 $t$，该顾客只能在编号为 $[l,r]$ 的商店购物，且只能购买特殊商品或进货时间为 $[t-d+1,t]$ 的商品，问该顾客的最大满意度。

注意初始时刻为 $0$，且询问不会导致时间流逝。

对与区间询问最大异或和操作可以用可持久化字典树 $O(\log v)$ 解决，于是可以先 $O((n+m)\log v)$ 处理出只考虑特殊商品时每个询问的答案。

接下来考虑对时间建立线段树，同时将每个询问加入线段树，遍历线段树时更新答案。

对于修改即进货操作，考虑先对其根据商店编号进行排序，这样就可以使用可持久化字典树加离散化处理询问。

然后遍历线段树时处理完当前节点询问后可以根据修改的时间分配到左右子树处理，每次处理询问重建字典树即可。

时间复杂度 $O((n+m)\log v\log m)$。

不错的线段树分治练手题。

P1646 [国家集训队]happiness

最小割，二者取一式问题

给定一个 $n*m$ 的矩阵（座位表），要分文理科了，每位同学选文理科可分别获得一个喜悦值，如果某同学和其相邻的同学选了同样的科，那么将获得额外的一个喜悦值，求最大喜悦值。