2022.12 做题记录（II）
RyexAwl
·
2022-12-07 13:45:39
·
个人记录
2022.12.7
P3168 [CQOI2015]任务查询系统
题目链接
标签：数据结构，扫描线，线段树，可持久化线段树
简要题意
给定 m 个三元组，(s_i,e_i,p_i) ，满足 1\le s_i\le e_i\le n ，有 n 个询问 (x_j,k_j) 表示查询所有满足 s_i\le k_j\le e_i 的二元组中，p 前 k 小的和。
强制在线。
#### 题解
一种显然的离线做法是按时间维扫描线，而强制在线不带修直接把扫描线可持久化即可。
复杂度 $O(n\log n)$。
> 总结：
>
> - 对于可以离线扫描线的问题，可以考虑把扫描线可持久化。
### P4251 [SCOI2015]小凸玩矩阵
[题目链接](https://www.luogu.com.cn/problem/P4251)
标签：二分，最大流，二分图最大匹配
#### 简要题意
给定一个 $n\times m$ 的矩阵 $A$，满足 $n\le m$，求从中选出恰好 $n$ 个不同的格子满足每行每列至多选一个格子，选出的 $n$ 个格子上权值第 $k$ 大的数的最小值是多少。
$1\le k\le n\le m\le 250,1\le A_{i,j}\le 10^9$。
#### 题解
考虑二分答案。考虑如何判定。问题转化为判定是否存在一种合法的选取格子的方案满足所选权值 $>x$ 的格子数量小于 $k$。对于本题选格子的模型有一个很典的转化为二分图选匹配的模型，进而直接转化为求最小费用最大流。但是复杂度太高，过不去。但是我们可以有更好的转化，转化为判定是否存在一种合法的选取格子的方案满足所选权值 $\le x$ 的格子数量大于等于 $n-k+1$，而其对应到二分图中相当于求最大匹配，跑 dinic 即可。
复杂度 $O(n^2\sqrt{n}\log n)$。
> 总结：
>
> - 网格图每行至多选一个格子的模型，转化为二分图匹配。
>
> - 判定转化为更简单的最大流 / 二分图最大匹配。
### P3172 [CQOI2015]选数
[题目链接](https://www.luogu.com.cn/problem/P3172)
标签：数论，递推，$\gcd
简要题意
我们知道，从区间 [L,H] （L 和 H 为整数）中选取 N 个整数，总共有 (H-L+1)^N 种方案。小 z 很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的 N 个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小 z 会告诉你一个整数 K ，你需要回答他最大公约数刚好为 K 的选取方案有多少个。
#### 题解
$H-L\le 10^5$，该性质的作用是如果 $K>H-L$，那么一定不存在一种选的数的种数大于一种的方案满足 $\gcd$ 恰好为 $K$，可以直接判掉。
而对于 $\le H-L$ 我们可以很简单的处理，算 $\gcd$ 恰好为 $K$ 的很难，但算 $\gcd$ 是 $K$ 的倍数很简单。而对于选的种数大于一种的方案我们只用考虑所有不超过 $H-L$ 的数，倒着递推即可。
复杂度 $O(n\log n)$。
> 总结：
>
> - （没想到）若 $K>H-L$ 一定不存在一种选的数的种数大于一种的方案满足 $\gcd$ 恰好为 $K$。
>
> - $\gcd$ 恰好为 $k$ 转化为 $\gcd$ 是 $K$ 的倍数，倒着递推。（另一种处理方式是莫比乌斯变换）。
## 2022.12.10
### P6134 [JSOI2015]最小表示
[题目链接](https://www.luogu.com.cn/problem/P6134)
标签：DAG，连通性，bitset，递推 / 递归，贪心
#### 简要题意
对于一个 $N$ 个点（每个点从 $1$ 到 $N$ 编号），$M$ 条边的有向图，JYY 发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。
JYY 想知道，如果想要使得原图任意两点的连通性保持不变，我们最多能删掉多少条边呢？
$1\le N\le 3\times 10^4,0\le M\le 10^5$。
#### 题解
我们可以通过传递闭包 $g[x,y]$ 来表示点 $x$ 是否可达 $y$，我们希望删掉尽量多的边使得给定的 DAG 的传递闭包不变，将其转化为保留原图边的最小子集使得该 DAG 的传递闭包不变。
但是为了保证传递闭包等价，我们并不总是关心所有的连通关系，我们可以只关心其中一部分的连通关系，这里我们可以只关心原图中给定的 $M$ 条有向边 $(x,y)$，我们希望保留尽量少的边使得对于原图有向边点对 $(x,y)$，$x$ 仍然可达 $y$。
因为 DAG 的性质（只存在从前向后的边），所以我们可以考虑从后向前归纳的考虑。
即我们每次考虑的子问题可以刻画为拓扑序后 $i$ 个点及其内部的边，最少保留多少条边使其连通性不变。
如果增量一个拓扑序最小的点 $x$，那么我们只用考虑保留 $x$ 最少多少条出边。
而对于该问题我们可以把 $x$ 的所有出边按拓扑序从小到大排序为 $v_1,v_2,...,v_k$ 因为只有前面的点会影响后面的点，所以这里考虑从前向后思考或从后向前思考，从前向后思考，不难发现我们每次不能到达的拓扑序最小的点总是会被选，因此使用 bitset 维护 DAG 连通性即可。
复杂度 $O(\frac{nm}{w})$。
> 总结：
>
> - DAG 从后向前归纳子问题，每次增量一个拓扑序最小的点。
>
> - DAG 从前向后贪心选点。
>
> - 利用 DAG 拓扑序只有前面向后面连边的性质，从后向前和从前向后分别能带来不同的性质方便我们处理，两个思考方向都可以尝试一下。
>
### P3976 [TJOI2015]旅游
[题目链接](https://www.luogu.com.cn/problem/P3976)
标签：数据结构，轻重链剖分，线段树
#### 简要题意
给定一棵 $n$ 个点的点带权树，$q$ 次询问每次询问给定两个点 $x,y$ 与一个权值 $v$，要求你先回答从 $x$ 到 $y$ 的路径上先买宝物再卖掉的最大收益，然后再给路径上的所有点的点权加 $v$。
$1\le n,q\le 5\times 10^4$。
#### 题解
轻重链剖分。具体实现细节可以把 $x$ 跳的路径合并成一个 struct，$y$ 跳的路径合并成一个 struct 最后再合并两个 struct。
## 2022.12.11
### P6640 [BJOI2020] 封印
[题目链接](https://www.luogu.com.cn/problem/P6640)
标签：后缀数组，数据结构，线段树，二分
#### 简要题意
给出只包含小写字母 $a,b$ 的两个字符串 $s, t$，$q$ 次询问，每次询问 $s[l \dots r]$ 和 $t$ 的最长公共子串长度。
$|s|,|t|,q\le 2\times 10^5$。
#### 题解
考虑 $q=1$ 时怎么做，令字符串 $str=s+*+t$，对 $str$ 求后缀数组，枚举公共子串 $s[l,r]$ 的 $l$，固定 $l$ 后相当于在后缀数组中向前 / 向后找第一个 $t$ 中的下标后求 lcp，令 $g[i]$ 表示 $suf(i)$ 以 $i$ 开头的与 $t$ 的最长公共子段。
接下来有两种做法：
- 对于每个询问二分答案，check 答案是否 $\ge x$ 等价于查 $\max\limits_{l\le i\le r-x+1}(g[i])$ 是否 $\ge x$。复杂度 $O((n+q)\log n)$。
- 询问相当于查询 $\max\limits_{l\le i\le r}(\min(r-i+1,g[i]))$。按 $r$ 扫描线，把询问离线掉。分别维护第一类和第二类贡献的最大值，对于第一类贡献相当于维护最小左端点，使用 set 即可，第二类相当于 rmq，线段树维护即可。贡献的修改和变化可以差分掉。复杂度 $O((n+q)\log n)$。
> 总结：
>
> - 对于数据结构题不要忘记二分答案。
>
> - $\max\limits_{l\le i\le r}(\min(r-i+1,g[i]))$ 内部的取 $\min$ 非常烦，把 $\min$ 拆掉，分别维护两类贡献。贡献分段，扫描线掉即可。
>
## 2022.12.18
### P8330 [ZJOI2022] 众数
[题目链接](https://www.luogu.com.cn/problem/P8330)
标签：数据结构，根号分治（序列模型按出现次数），扫描线，众数
#### 简要题意
九条可怜是一个有超能力的女孩子，但她的超能力只能作用于一些奇怪的事情上。
有一天，可怜得到了一个序列 $a_1, a_2, \ldots, a_n$，她可以对这个序列使用一次超能力: 选择一个区
间 $[l, r]$（$1 \le l \le r \le n$）和一个整数 $k \in [-{10}^9, {10}^9]$，将区间内的所有数 $a_l, a_{l + 1}, \ldots, a_r$ 加上 $k$。
九条可怜很喜欢长得比较一致的序列，因此她希望最终的序列众数的出现次数尽可能多。给出序列 $a$，你需要输出最终序列的众数出现次数的最大值，并输出这个众数的所有可能取值。注意对于一个序列，众数的取值可能不止一个。
$1 \le T \le 20$，$2 \le n \le 2 \times {10}^5$，$1 \le a_i \le {10}^9$，保证 $\sum n \le 5 \times {10}^5$，且 $a_i$ 不全相等。
#### 题解
不难将问题转化为：对于原序列中出现过的所有权值求出 $f(x)$ 表示在序列中选一个区间 $[l,r]$ 使得 $[l,r]$ 中众数出现的次数加上 $[l,r]$ 外 $x$ 的出现次数的最大和。
输出最大的 $f(x)$ 以及所有取到最大的权值 $x$。
算法一：对于每种权值 $x$，枚举 $[l,r]$，复杂度 $O(n^3)$，期望得分 $20$。
算法二：把众数的限制放掉，枚举“众数” $y\ne x$，如果 $x$ 在序列中出现了 $cnt[x]$ 次，相当于找一个区间最大化 $cnt[x]$ 减去区间中 $x$ 的出现次数加上该区间 $y$ 的出现次数，构造一个新序列 $b$，若 $a_i=x$，那么 $b_i=-1$，若 $a_i=y$ 那么 $b_i=1$ 否则 $b_i=0$，求最大子段和即可。如果 $m$ 是数的种数，那么复杂度为 $O(nm^2)$。结合算法一，期望得分 $40$。
考虑优化算法二。按出现次数分治，称出现次数 $\le B$ 的为“小数”，出现次数 $>B$ 的为“大数”。
将 $x,y$ 分类：
- 小数对小数。
- 大数对大数。
- 小数对大数。
其中所有包含大数的部分的处理都比较简单，这里不展开讲。
考虑如何解决小数对小数的 part，这里用到的一个重要的性质是一个序列的最大子段和取到的区间 $[l,r]$，$l,r$ 要么“顶到边界（比如对于长为 $n$ 的序列等于 $1$ 或 $n$）” ,要么就是与负数相邻不能扩展。
因此考虑对每种小数 $x$ 枚举 $[l,r]$ 顶到的两个边界（即每种小数 $x$ 付出 $cnt[x]^2$ 的时间代价）。
因为每种数出现的次数不超过 $O(B)$，所以这里枚举的时间代价不超过 $O(nB)$（看成遍历 $1\sim n$ 中的位置，如果 $a[i]$ 是小数就遍历其所有取 $a[i]$ 的位置）。
考虑扫描线枚举点对（遍历 $1\sim n$ 中的位置，如果 $a[i]$ 是小数就遍历其所有取 $a[i]$ 的位置），我们需要维护区间众数类状物。
但是因为我们只用维护出现次数 $\le B$ 的，所以有很好的处理方法。在扫描线过程中维护 $S[i]$ 表示 $i$ 到 $r$ 的众数，增量更新，这里的复杂度同样不超过 $O(nB)$。（因为 $\sum S[i]\le nB$，每次更新让 $\sum S[i]$ 至少增加一。）
> 总结：
>
> - （trick）对于形如 $\max(\max()+...)$ 的问题可以把内层 $\max$ 放掉（本题即实际上可以不在意众数的限制）。
>
> - （trick）按出现次数分治。
>
> - （trick）按出现次数分治后。枚举所有小数 $x$，$\sum cnt[x]^2$ 的代价不超过 $O(nB)$。
>
> - （trick）扫描线枚举小数点对方便维护其他信息。
## 2022.12.19
### P8329 [ZJOI2022] 树
[题目链接](https://www.luogu.com.cn/problem/P8329)
标签：计数，动态规划，容斥，子集反演，数学
#### 简要题意
九条可怜是一个喜欢树的女孩子，她想生成两棵均有 $n$ 个节点的树。
第一棵树的生成方式是：
1. 节点 $1$ 作为树的根。
2. 对于 $i \in [2, n]$，从 $[1, i - 1]$ 中选取一个节点作为 $i$ 的父亲。
第二棵树的生成方式是：
1. 节点 $n$ 作为树的根。
2. 对于 $i \in [1, n - 1]$，从 $[i + 1, n]$ 中选取一个节点作为 $i$ 的父亲。
九条可怜希望对于任意 $i \in [1, n]$，若第一棵树中的节点 $i$ 为叶子，那么第二棵树中的节点 $i$ 为非叶子；若第一棵树中的节点 $i$ 为非叶子，那么第二棵树中的节点 $i$ 为叶子。一个节点被称为叶子当且仅当没有节点的父亲是它。
九条可怜希望你统计生成两棵树的方案数是多少。具体地，你需要对于所有 $n \in [2, N]$ 都计算方案数。两种方案不同当且仅当存在一棵树中的一个节点 $i$，两种方案中它的父亲不同。因为答案可能很大，你只需要输出答案对 $M$ 取模后的结果。
$2 \le N \le 500$，$10 \le M \le 2^{30}$。
#### 题解
令 $f(S)$ 表示第一棵树叶子集合恰好是 $S$ 的方案数，$g(S)$ 表示第二棵树叶子集合恰好是 $S$ 的方案数，那么相当于计算：
$$
\sum_{S\cap T=\empty,S\cup T=\{1,2,3,...,n\}}f(S)\times g(T)
$$
##### 算法一
令 $f[i,S]$ 表示考虑 $1\sim i$ 叶子集合恰好是 $S$ 的方案数。复杂度 $O(n2^n)$，期望得分 $20$。
##### 算法二
注意到，钦定一个集合是叶子是好做的（第一棵树为每个点前面未被钦定是叶子的个数乘起来，第二棵树类似），考虑钦定集合是叶子容斥（子集反演）。
令：
$$
f'(S)=\sum_{S\subseteq T}f(T),g'(S)=\sum_{S\subseteq T}g(T)
$$
根据子集反演：
$$
f(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}f'(T),g(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}g'(T)
$$
考虑枚举 $(A,B)$ 计算贡献，那么：
$$
\sum_{S\cap T=\empty,S\cup T=\{1,2,3,...,n\}}f(S)\times g(T)=\sum_{A,B,A\cup B=\{1,2,3,...,n\}}2^{|A\cap B|} \times (-1)^{|A|+|B|-n}f'(A)g'(B)
$$
即对于任意 $1\le p\le n$，在两棵树中的至少一棵树满足 $p$ 是叶子的每个方案，如果第一棵树有 $i$ 个叶子，第二棵树有 $j$ 个叶子，那么贡献的系数为 $2^{|A\cap B|}\times (-1)^{|A|+|B|-n}$。
将 $(-1)^n$ 提出来，考虑 dp 出带 $2^{|A\cap B|}\times (-1)^{|A|+|B|}$ 的方案，即：
$$
\sum_{A,B,A\cup B=\{1,2,.,...,n\}}2^{|A\cap B|}\times (-1)^{|A|+|B|}\prod_{i=1}^n\left(\sum_{j<i}[j\not\in A]\right)\left(\sum_{j>i}[j\not \in B]\right)
$$
那么我们考虑枚举 $2\times m$ 的 $01$ 矩阵（即 $A,B$ ），满足每列至少一个 $1$，从左向右扫描线即可计算贡献。
```cpp
// 确定了集合 A,B 后如何计算贡献（实际上我们要看成枚举 a,b,k，只有最终状态 k 取 0 的是合法状态）
int calc(int a[],int b[],int k) {
int j = 0,res = 1;
for (int i = 1; i <= n; i++) {
if (i > 1) res *= j;
if (i < n) res *= k - (b[i] ^ 1);
if (a[i] && b[i]) res *= 2;
if (a[i]) res *= -1;
if (b[i]) res *= -1;
k -= (b[i] ^ 1); j += (a[i] ^ 1);
}
return res;
}
```
对于单个 $n$ dp 可以做到 $O(n^3)$，但是我们需要更快，我们希望尽可能重复的利用 dp 信息。
考虑把 $n$ 特殊处理，只枚举 $1\sim n-1$ 的贡献：
```cpp
int calc(int a[],int b[],int k) {
int j = 0,res = 1;
for (int i = 1; i <= n - 1; i++) {
if (i > 1) res *= j;
res *= k - (b[i] ^ 1);
if (a[i] && b[i]) res *= 2;
if (a[i]) res *= -1;
if (b[i]) res *= -1;
k -= (b[i] ^ 1); j += (a[i] ^ 1);
}
return res;
}
```
固定 $n$ 时单独转移即可。
```cpp
void main() {
scanf("%d%d",&n,&mod);
rep(i,0,n) f[0][0][i] = 1;
rep(i,0,n - 1) {
memset(f[(i + 1) & 1],0,sizeof f[(i + 1) & 1]);
if (i + 1 >= 2) {
int ans = 0;
rep(j,0,i) rep(k,0,n-i) rep(a,0,1) rep(b,0,1) {
if (!(a + b)) continue;
int nj = j + (a ^ 1),nk = k - (b ^ 1);
if (nk != 0) continue;
int cur = f[i & 1][j][k];
if (i > 0) cur = 1ll * cur * j % mod;
if (a && b) cur = 1ll * cur * 2 % mod;
if (a) cur = (mod - cur) % mod;
if (b) cur = (mod - cur) % mod;
ans = (ans + cur) % mod;
}
if (((i + 1) & 1)) ans = (mod - ans) % mod;
printf("%d\n",ans);
}
rep(j,0,i) rep(k,0,n-i) rep(a,0,1) rep(b,0,1) {
if (!(a + b)) continue;
int nj = j + (a ^ 1),nk = k - (b ^ 1);
if (nk < 0) continue;
int cur = f[i & 1][j][k];
if (i > 0) cur = 1ll * cur * j % mod;
cur = 1ll * cur * nk % mod;
if (a && b) cur = 1ll * cur * 2 % mod;
if (a) cur = (mod - cur) % mod;
if (b) cur = (mod - cur) % mod;
f[(i + 1) & 1][nj][nk] = (f[(i + 1) & 1][nj][nk] + cur) % mod;
}
}
}
```
> 总结：
>
> - 把答案写成集合函数求和的形式，方便利用集合的处理方式。
>
> - 如果钦定某个东西好做，考虑容斥。
>
> - 容斥可以合并。
>
> - 计数问题可以写出形式化的式子，方便思考 dp（即不用考虑太多的组合意义，直接看成权值和统计的模型）。
>
> - （泛 trick）dp 技巧。（dp 的状态机理论，这里的理解方式可以类比一下 ac 自动机的 dp，构造一个自动机，枚举输入（ac 自动机中是枚举字符串））一般化的技巧可以看成考虑如何 check / 计算权值，令 $f[i,xxx]$ 表示考虑前 $i$ 个 ... 输入到自动机走到 xxx 节点的所有输入当前的权值和 / $\max$ / $\min$。
>
> - （泛 trick）不止枚举合法的 $a,b$，同时枚举 $k$ 方便计算贡献。即多枚举一些东西（比如本题中是序列的一些性质，有点“费用提前”的意思，把原来需要扫一遍才能知道的东西直接预先知道）方便 trick。
>
## 2022.12.20
### P6630 [ZJOI2020] 传统艺能
[题目链接](https://www.luogu.com.cn/problem/P6630)
标签：数据结构，线段树，动态规划，懒标记
#### 简要题意
Bob 喜欢线段树。
众所周知，ZJOI 的第二题有很多线段树。
Bob 有一棵根为 $[1, n]$ 的广义线段树。Bob 需要在这个线段树上执行 $k$ 次区间懒标记操作，每次操作会等概率地从 $[1, n]$ 的所有 $\dfrac{n(n+1)}{2}$ 个子区间中随机选择一个。对于所有在该次操作中被访问到的非叶子节点，Bob 会将这个点上的标记下推；而对于所有叶子节点（即没有继续递归的节点），Bob 会给这个点打上标记。
Bob 想知道，$k$ 次操作之后，有标记的节点的期望数量是多少。
$1\le n\le 2\times 10^5,1\le k\le 10^9$。
#### 题解
根据期望的线性性质可以转化为 $k$ 次操作后每个节点上有标记的概率和，这样我们就把贡献独立到每个节点上了。
对于线段树的一个节点 $u$，其表示的区间为 $[l,r]$，对于一次操作 $[ql,qr]$ 定义点 $u$ 的覆盖状态：
- 若 $[l,r]\cap [ql,qr]=\empty$，称 $[ql,qr]$ 未覆盖 $u$。
- 若 $[l,r]\subseteq [ql,qr]$，称 $[ql,qr]$ 全覆盖 $u$。
- 若 $[l,r]\cap [ql,qr]\ne \empty$ 且 $[l,r]\not \subseteq [ql,qr]$，称 $[ql,qr]$ 半覆盖 $u$。
对于一次区间修改，树上任意节点可能是以下五种状态之一：
- 未覆盖且可能从祖先得到下传的标记。
- 未覆盖且不可能从祖先得到下传的标记。
- 全覆盖且被访问到。
- 全覆盖且未被访问到。
- 半覆盖。
分别令 $a_u,b_u,c_u,d_u,e_u$ 分别表示有多少个区间 $[ql,qr]$ 满足对 $[ql,qr]$ 操作 $u$ 的状态恰好是（未覆盖且可能从祖先得到下传的标记，未覆盖且不可能从祖先得到下传的标记，全覆盖且被访问到，全覆盖且未被访问到，半覆盖）
如果操作区间是 $Q$，当前节点区间是 $U$，父节点区间是 $F$，那么：
- 未覆盖且可能从祖先得到下传的标记：$Q\cap U=\emptyset,Q\cap F\ne \emptyset$。
- 未覆盖且不可能从祖先得到下传的标记：$Q\cap F=\emptyset$。
- 全覆盖且被访问到：$U\subseteq Q$ 且 $F\not \subseteq Q$。
- 全覆盖且未被访问到：$F\subseteq Q$。
- 半覆盖：$ Q\cap U \not= \emptyset,U\not \subseteq Q $ 。
这些均可以 $O(1)$ 计算。
对于点 $u$，令 $f[i]$ 表示进行恰好 $i$ 次操作后 $u$ 被打上标记的方案数，$g[i]$ 表示进行恰好 $i$ 次操作后 $u$ 或 $u$ 的祖先被打上标记的方案数，$h[i]$ 表示恰好 $i$ 次操作后 $u$ 和 $u$ 的祖先上均没有标记的方案数。
初始 $h[0]=1$。
转移可以写成矩阵，矩阵加速即可。
复杂度 $O(27\times n\log k)$。
> 总结：
>
> - 期望的线性性质，转成概率求和。
>
> - 广义线段树懒标记处理技巧。
>
> - 一个节点上的标记要么是新打上的要么是从祖先（注意不只是父节点）传下来的，利用此性质设计状态。
>
> - 矩阵乘法优化 dp。
## 2022.12.21
### P5280 [ZJOI2019]线段树
[题目链接](https://www.luogu.com.cn/problem/P5280)
标签：数据结构，动态规划，线段树，懒标记
#### 简要题意
九条可怜是一个喜欢数据结构的女孩子，在常见的数据结构中，可怜最喜欢的就是线段树。
线段树的核心是懒标记，下面是一个带懒标记的线段树的伪代码，其中 $tag$ 数组为懒标记：
其中函数 $\operatorname{Lson}(Node)$ 表示 $Node$ 的左儿子，$\operatorname{Rson}(Node)$ 表示 $Node$ 的右儿子。
现在可怜手上有一棵 $[1,n]$ 上的线段树，编号为 $1$。这棵线段树上的所有节点的 $tag$ 均为$0$。接下来可怜进行了 $m$ 次操作，操作有两种：
- $1\ l\ r$，假设可怜当前手上有 $t$ 棵线段树，可怜会把每棵线段树复制两份（$tag$ 数组也一起复制），原先编号为 $i$ 的线段树复制得到的两棵编号为 $2i-1$ 与 $2i$，在复制结束后，可怜手上一共有 $2t$ 棵线段树。接着，可怜会对所有编号为奇数的线段树进行一次 $\operatorname{Modify}(root,1,n,l,r)$。
- $2$，可怜定义一棵线段树的权值为它上面有多少个节点 $tag$ 为 $1$。可怜想要知道她手上所有线段树的权值和是多少。
$n\le 10^5,m\le 10^5$。
#### 题解
注意到每棵线段树的结构都是相同的，考虑对每个点维护其在多少棵线段树内有标记。
令 $f_u$ 表示当前点 $u$ 在多少棵线段树中有标记，$g_u$ 表示 $u$ 及 $u$ 的祖先在多少棵线段树中有标记。
类似 P6630 [ZJOI2020] 传统艺能，把一次区间操作中涉及到的点分五类，分别处理转移。
```cpp
// modify 函数没访问到的点均是未覆盖
void modify(int u,int l,int r) {
if (t[u].l == l && t[u].r == r) {
// u 被全覆盖且被访问，u 子树内其他点被全覆盖且未访问
t[u].lazy = 1;
return;
}
// u 被半覆盖
int mid = (t[u].l + t[u].r) >> 1; pushdown(u);
if (r <= mid) {
modify(u << 1,l,r);
// 右儿子未被覆盖且可能得标记，右儿子子树内其他点未被覆盖且不可能得标记
return;
}
if (l > mid) {
modify(u << 1 | 1,l,r);
// 左儿子未被覆盖且可能得标记，左儿子子树内其他点未被覆盖且不可能得标记
return;
}
modify(u << 1,l,mid); modify(u << 1 | 1,mid + 1,r);
}
```
转移可以写成单点修改，子树加 / 乘，直接在线段树上维护即可（一开始我的做法是再写一棵线段树维护 dfs 序上的信息，但是并没有必要）。
复杂度 $O(m\log n)$。
> 总结：
>
> - 懒标记统计 trick。给定若干次区间操作，维护懒标记状态信息的问题，可以通过对点的五个分类讨论加上前一轮中的懒标记状态信息递推新的懒标记状态。换句话说通过维护 $f,g,h$，然后进行五个分类讨论可以维护出一轮的线性变换。
>
> - 线段树非 leafy tree 的信息维护。
>
> - 注意空间，对于左儿子 $2k$ 右儿子 $2k+1$ 的线段树如果对叶子节点也访问儿子要开 $8$ 倍空间，否则会 RE。
## 2022.12.23
### P3975 [TJOI2015]弦论
[题目链接](https://www.luogu.com.cn/problem/P3975)
标签：字符串，后缀树，后缀数组，笛卡尔树
#### 简要题意
给定一个长度为 $n$ 的字符串 $S$，求出其第 $k$ 小的子串，同时给定 $t$：
- 若 $t=0$，表示不同位置的相同子串算作一个。
- 若 $t=1$，表示相同位置的相同子串算作一个。
$1\le n\le 5\times 10^5,0\le t\le 1,1\le k\le 10^9$。
#### 题解
对串 $S$ 建立重构树，按先序顺序遍历子串：
- $t=0$：遍历到 $u$ 时，如果 $len[u]-len[fa[u]]<k$，令 $k:=k-len[u]-len[fa[u]]$，继续遍历。否则说明答案就在 $u$ 与 $u$ 父亲的边上，枚举即可。
- $t=1$：遍历到 $u$ 时，令 $sz[u]$ 表示 $u$ 字数内叶子的个数。如果 $sz[u]\times (len[u]-len[fa[u]])<k$，令 $k:=k-sz[u]\times (len[u]-len[fa[u]])$，继续遍历。否则说明答案就在 $u$ 与 $u$ 父亲的边上，枚举即可。
复杂度 $O(n)\sim O(n\log n)$，主要取决于求后缀数组的复杂度。
### P4094 [HEOI2016/TJOI2016]字符串
[题目链接](https://www.luogu.com.cn/problem/P4094)
标签：字符串，数据结构，二分答案，后缀数组，主席树
#### 简要题意
给定一个长度为 $n$ 的字符串 $s$，$m$ 次询问，每次询问给定两个区间 $[a,b],[c,d]$，询问 $s[a,b]$ 的 **所有子串** 与 $s[c,d]$ 的 LCP 最长是多少。
$1\le n,m\le 10^5,a\le b,c\le d,1\le a,b,c,d\le n$。
#### 题解
即询问：
$$
\max\limits_{i\in [a,b]}(\min(\mathrm{lcp}(i,c),d-c+1.b-a+1))
$$
考虑二分答案。求后缀数组。不难发现每次 check 可以转化为求：
$$
\sum_{i=l}^{r}[sa[i]\in [a,b-k+1]]
$$
使用主席树维护二维数点即可。
复杂度 $O(m\log ^2n+n\log n)$。
> 总结:
>
> - 不要忘了二分答案。（同 P6640 [BJOI2020] 封印 ）
>
> - 主席树维护二维数点。