异或方程组

字符串 2

字符串 3

字符串 4

可持久化数组

主席树

拆点

洛谷p2447

异或方程组

异或方程组的模板题

SP1812

后缀数组，后缀自动机

给定 $n$ 个串，求 $n$ 个串的 $\text{LCS}$。

先考虑两个串匹配的情况。考虑将一个串压入 $\text{SAM}$，另一个串在 $\text{SAM}$ 上匹配。

如果存在 $ch[pos][c]$，则直接匹配，且匹配长度 $+1$。否则考虑尽可能地保留后缀，于是不断跳 $\text{parent}$ 树。

由于当前串的后缀与当前等价类地某个串匹配，而该等价类的最短串长度大于父节点等价类中最长串，于是当前串一定能与父节点最长串匹配。

于是跳 $\text{parent}$ 树过程中如果遇到 $ch[pos][c]$ 存在的情况，则跳到 $ch[pos][c]$ 结点，匹配长度变为 $len_\text{pos}+1$。

每次失配向上跳使得匹配长度变短，而匹配长度最多增加 $|T|$ 次，于是失配的均摊复杂度为 $O(1)$。时间复杂度 $O(|S|)$。

接下来考虑 $n$ 个串匹配的情况。先将一个串压入 $\text{SAM}$，其他所有串在 $\text{SAM}$ 上匹配。

对每个串，记录每个结点匹配的答案，然后每个结点取该结点所有匹配答案的最小值，然后所有结点的最大值即为所求答案。

注意 $\text{parent}$ 树的子节点可以将答案贡献给父节点，可以每次匹配后根据拓扑序转移答案。时间复杂度 $O(\sum |S|)$。

后缀自动机基础题。

CodeForces 12D Ball

标签

线段树

题意

有 $n$ 个人，每个人有三个属性($a_i,b_i,c_i$)。如果一个人的三个属性均小于另一个人的，那么他将告辞。问最后有多少人告辞。$1\le n\le 5\times 10^5$

题解

首先将第一维离散化，第二维从大到小排序，以第一维为坐标在线段树中插入第三维的值。由于逐个插入，第二维一定递减；对于每个新插入的数只要保证它插入位置后面的区间最大值比这个数小就不会告辞。时间复杂度 $O(n\log n)$

评价

三维偏序用线段树解，感觉非常妙，线段树的应用十分灵活。