CTime_Pup_314

题面描述

支持修改点权，维护子树内和链上的的背包。

题解

用线段树维护一下背包就好了，但不管怎么 \(O(m^2)\) 常数的更新的复杂度避免不了

题面描述

求若干条树链的并

题解

做法有很多，首先是用容斥把树链的并转化为树链的交，或者是建出虚树，利用 \(dfs\) 序虚树求值，但两者细节较多，所以直接用线段树的区间覆盖标记了

题面描述

询问区间内所有满足重排后连续的区间个数

题解

第一道真正利用线段树历史标记的题

终于知道线段树统计子区间问题的一种方法了

结合 [CERC2017]Intrinsic Interval 食用更佳

考虑把操作离线，枚举每个右端点 \(r\)，对于左端点 \(l\) 记录 \(cnt+l-r\)，\(cnt\) 为区间 \([l,\ r]\) 的满足 \(|a-b|<1\) 的无序数对 \((a,\ b)\) 的数量，当一个区间合法当且仅当 \(cnt+l-r=0\)，其余情况 \(cnt+l-r\le r\)，在线段树上维护最大值和最大值出现次数，每次右端点移动时用合法的相邻的数统计一下即可

题面描述

求一个区间被包含的最短重排后连续区间。

题解

判断区间是否连续有一个十分显然的做法，即判断 \(max-min=r-l\)，但是这样的做法并不能很好维护

但我们发现该区间重排后为等差数列，所以我们可以认为一个区间满足 \(|a-b|\le 1\) 的无序数对 \((a,\ b)\) 个数为 \(r-l\)，那么这个区间合法

题面描述

动态维护树的重心

题解

树的重心就是满足以重心为根时子节点所在最大子树最小的点

树的重心的性质

• 树的重心为根是子节点所在最大子树大小不超过整体的一半
• 树的所有点到重心的简单路径和最小
• 两个联通块合并时，新的树的重心必定在原来两个联通块树的重心的简单路径上

简单证明一下

题目描述

求字符串每个位置被包含且出现只有一次的最短子串长度。

题解

\(SAM\) 部分很好想，关键是如何用线段树维护，我们假设当前位置为 \(r\)，对应的 \(np\) 节点为 \(x\)，则有左端点 \(l\ =\ r-maxlen(parent(x))\) 在区间 \([l,\ r]\) 内最小值为 \(maxlen(parent(x))+1\) 并且对于区间 \([1,\ l-1]\) 每个位置 \(i\) 来说，答案更新为 \(r-i+1\)，前面的信息很好维护，对于后面的位置来说，我们只需要做到单点查询，所以可以把 \(i\) 挪到外面，用另外一颗线段树维护即可

题面描述

给定n个模板串，以及m个查询串，查询每一个查询串是多少个模板串的子串

题解

广义后缀自动机匹配和子树数颜色，后者用启发式合并即可

广义后缀自动机的拓扑序又双叒叕挂掉了，上次口胡的解决方法错了，我不想建树啊，谁来救救蒟蒻啊啊啊啊

题面描述

求两个字符串最短不公共子序列和子串

题解

我们需要两个自动机，一个可以接受所有子串，另一个可以接受所有子序列，前者我们可以使用 \(SAM\)，后者我们要构造一个叫做序列自动机的东西

序列自动机的构造不难理解，记录每个字符上一个出现位置，连转移边即可，构造复杂度为 \(O(n|S|)\)，感性理解下就是每一次加入的复杂度等价为从这一次加入到上一加入之间有多少字符，单看每个字符这个整体求和后是 \(O(n)\)，字符集大小为 \(|S|\)，所以复杂度为 \(O(n|S|)\)

题目描述

给定子串集合 \(A\) 和 \(B\)，和支配关系，构造最长目标串满足由 \(A\) 构成，对于相邻 \(A\)，后一个存在前缀为 \(B\)，且被 \(A\) 支配

题解

很明显，这道题的目的是优化建图，由于在练习 \(SAM\)，所以就不考虑 \(SA\) 了

对于原串建一颗后缀树，发现题目中的建边正好是对于后缀树子树的连边，直接 \(DFS\) 序搞一下线段树优化建图跑个拓扑就行了

但注意，对于倍增向上跳的节点对于后 \(20\) 分不完全合法，只向部分连边，所以当时口胡的做法是每个节点按长度在排个序，再搞一次线段树优化建图就行了

题面描述

支持区间向单点连边的单源最短路问题。

题解

线段树优化建图模板题，建立两个线段树，一个由内向外连，一个由外向内连即可，具体细节就按照线段树区间操作口胡一下就好了