更佳的阅读体验：2023 国庆集训 Day 3A 笔记，本文同步发表于 洛谷博客。
以下内容为个人总结，如有错误或您有不同见解，欢迎指出。
线段树
- 多用于辅助数据结构。
- 也有应用线段树思维的分治。
矩形叠加问题
给定一个 $n \times n$ 的二维平面上的 $m$ 个矩形，对于 $i=1,2,\cdots n$，求所有满足 $x=i$ 的整点中最多被矩形覆盖的整点被多少个矩形覆盖。$n, m \le 10^5$。
把 $x$ 维看作是时间，$y$ 维看成一个一维的序列 $a_1, a_2, \cdots a_n$，问题变成：
- 对于一个 $x \in [x_l, x_r]$，$y \in [y_l, y_r]$ 的矩形，相当于是在 $x_l$ 时间对区间 $[y_l, y_r]$ 的 $a$ 全体加 $1$，在 $x_r + 1$ 时间对区间 $[y_l, y_r]$ 的a全体减 $1$。
- 然后对于时间 $1 \cdots n$，询问一下全局所有 $a$ 的最大值。
LOJ Round #6 - 花火
- 第二种操作在什么时候执行效果都是一样的，所以考虑一开始就交换两个数。
- 对于一个排列，交换相邻的两个数从而排序所需要的数是确定的——逆序对数。所以我们的问题变成交换两个数使得逆序对个数最少。
- 如果我们交换第 $l$ 个数和第 $r$ 个数，只需要考虑 $[l, r]$ 之内的逆序对改变，因为其他逆序对都没变。
- 不失一般性假设 $h_l > h_r$（反之则没必要交换），减少的逆序对是 $[l, r]$ 中值在 $[h_r + 1, h_l - 1]$ 的数的个数 $\times 2$。
- 也就是说对于每个 $h_i$，在二维平面中画一个点 $(i, h_i)$，我们想找两个点组成矩形的左上角和右下角，能框住最多多少个点。
- 所以现在题面变成，给定平面上 $n$ 个点 $(x_1, y_1) \cdots (x_n, y_n)$，求两个点分别作为左上角和右下角最多能框住多少个点。
- 那么如果 $x_i > x_j, y_i > y_j$，则 $(x_j, y_j)$ 一定不会作为左上角。所以我们可以找出一条从左下到右上的、$x$ 坐标单调递增、$y$ 坐标单调递增的可以作为左上角的点的序列 $s_1, s_2, \cdots, s_k$。
- 同理可以得到一条从左下到右上的、$x$ 坐标单调递增、$y$ 坐标单调递增可以作为右下角的点的序列 $p_1, p_2, \cdots, p_k$。
- 可以发现每一个点 $(x_i, y_i)$ 会对左上角位于一个区间 $s_l, \cdots, s_r$ 和右下角位于一个区间 $p_x, \cdots, p_y$ 的所有矩形有 $1$ 的贡献，直接用之前的矩形叠加问题即可解决。
线段树分治
- 考虑一类问题，给你一堆加入、删除操作，维护某个东西。
- 如果加入、删除的数据结构非常困难，但是加入、撤销上一次加入很简单，且问题离线，就可以用 $\log$ 的时间代价使用一种简便的方法。
- 具体方法是考虑某一元素的加入时间 $st$，和删除时间 $ed$。对时间建立一个线段树，把每一个元素的时间段 $[st, ed]$ 放在线段树上变成 $\log$ 个区间，然后在线段树上从上到下直接使用加入、撤销数据结构维护答案。
动态连通块个数
维护一张无向图 $q$ 次操作，每次加入一条边或删一条边，维护连通块个数。$q \le 10^5$。
- 对每一条边存在的时间建立线段树。
- 考虑线段树分治，对每一条边计算加入删除时间，然后在线段树上从根往下只需要支持加入一个边，撤销上一条边。此时只需要使用按秩合并即可以 $O(n \log^2 n)$ 的复杂度解决。
HASH
Example 1
给定串 $S$ 和 $q$ 次询问，每次询问两个位置 $l_1, l_2$ 的最长公共前缀。$\lvert S \rvert, q \le 3 \times 10^5$。
- 对于字符串，在 $i$ 的 HASH $h_i = (\sum_{j = 0} ^ i a^{i - j} s_j) \mod p$，则对于一个区间 $[l, r]$ 有 $\text{hash}([l, r]) = (h_r - h_{l - 1}) a^{r - l} \mod p$。
CF1017E
- 考虑求出凸包后，用一些旋转、平移无关的量表示。
- 一种可行的方法是，考虑凸包上相邻的三个点，把这个三角形的三边长度作为参数构建一个序列，然后只需要看两个序列是否平移同构，直接 HASH 即可（也可以KMP）。
- 这题提示我们，使用 HASH 的一个要点是找到一种表示。
CCPC2023 D（矩阵 HASH）
给定一个有 $m$ 种括号的长度为 $n$ 的序列，每种括号分为左右两种，有 $q$ 次操作，每次操作有两种情况：
- 修改一个位置的括号类型（哪一种，左 / 右）。
询问一段区间 $[l, r]$ 的子串是否是一个合法的括号序列，合法的括号序列定义如下：
- 空串是合法的括号序列。
- 如果 $A$ 和 $B$ 都是合法的括号序列，那么 $AB$ 也是。
- 如果A是合法的括号序列，那么 $(A), [A], )A(, ]A[$ 也是合法的括号序列。
$n, q \le 10^5$。
- 给每一种括号随机对应一对矩阵，第 $i$ 种括号的左括号对应矩阵 $T_i$ ，第 $i$ 种括号的右括号对应矩阵 $T_i^{-1}$（$T_i$ 的逆）。
- 这样的话一个括号序列 $A$ 合法则对应矩阵连乘是单位阵，反之则以极大概率不是单位阵。
- 用线段树维护矩阵连乘即可。
UOJ552 - 同构判定鸭
给定两张有向图 $G_1$，$G_2$，每条边上有小写字母。定义一个串 $S$ 是好串当且仅当 $S$ 作为一条路径上的字母序列在 $G_1$ 中出现次数等于其在 $G_2$ 中的出现次数。
求出最短的非好串（同样短按字典序），没有输出 $\texttt{Same}$。
$n \le 500, m \le 3000$。
- 对于给定长度 $l$，求所有 $\le l$ 的串出现次数是否一样？
- 二分答案 $l$，判断是否所有小于 $l$ 的路径的字符串集合一样，上界 $n_1 + n_2$。
- 令 $f_{i,j}$ 表示从 $i$ 出发，所有长度等于 $j$ 的路径的字符串集合的 HASH， $g_{i, j}$ 表示从 $i$ 出发，所有长度等于 $j$ 的路径的字符串的集合大小。
- 对于每个长度、每个点记录所有以它为起点的所有串的 HASH 和，然后比对所有点的 HASH 和即可。
- 对于计算答案，我们可以先计算出答案长度 $L$（可以证明不超过 $n_1 + n_2$），然后按照字典序枚举每一位 $i$，用之前算过的，每个点长度为 $L - i$ 的串 HASH 之和来验证。
- 这里的 HASH 由于是串的和，所以不能使用传统的 HASH 方法（多项式hash）。因为多项式 HASH 是按位独立的，即 $H(\texttt{ab}) + H(\texttt{cd}) = H(\texttt{ad}) + H(\texttt{cb})$。
- 可以使用矩阵 HASH。
矩阵 HASH
- 对于每个字母 $c$，随机一个低维矩阵 $M_c$。
- 对于一个字符串，HASH 就是每一位对应的 $M$ 按顺序乘积。
- 这样的 HASH 具有非常强的安全性（不满足交换，且不按位独立，同时自然 HASH 空间大），但是坏处就是计算常数大。