「Ynoi2011」成都七中
给出一棵包含 n 个点的树,每个节点有一种颜色 c_i。
有 m 次查询,每次查询给出三个参数 l, r, x,表示询问只保留编号在 [l, r] 范围内的点时,x 所在连通块的颜色种类数。
数据范围:1 \leq n, m \leq 10^5,1 \leq c_i \leq n,1 \leq l \leq x \leq r \leq n。
时空限制:1s / 250MiB。
给出一棵包含 n 个点的树,每个节点有一种颜色 c_i。
有 m 次查询,每次查询给出三个参数 l, r, x,表示询问只保留编号在 [l, r] 范围内的点时,x 所在连通块的颜色种类数。
数据范围:1 \leq n, m \leq 10^5,1 \leq c_i \leq n,1 \leq l \leq x \leq r \leq n。
时空限制:1s / 250MiB。
对于一个包含字符串 s_1, s_2, \dots, s_k 的字符串可重集 T,定义 T 的价值为
给出一个长度为 n 的字符串 S,下标从 1 到 n。有一个初始为空的字符串集合 T。
有 m 次操作,每次操作给出两个正整数 l, r (1 \leq l \leq r \leq n),你需要将字符串 S[l : r] 的所有前缀都加入集合 T。形式化地,对于所有 l \leq i \leq r,你需要将 S[l : i] 加入集合 T。
每次操作过后,你都需要求出此刻集合 T 的价值。答案对 10^9 + 7 取模。
数据范围:1 \leq n, m \leq 10^5。
时空限制:8s / 512MiB。
给出一棵包含 n 个节点的树,以 1 为根,边带权。
定义 \mathrm{dep}_x 表示节点 x 到根的简单路径上的边权和。
有 Q 次查询,每次查询给出两个参数 l, r,对于所有满足 l \leq i, j \leq r 的二元组 (i, j),你需要求出有多少种不同的 \mathrm{dep}_{\mathrm{LCA}(i, j)}。
数据范围:1 \leq n \leq 10^5,1 \leq Q \leq 5 \times 10^5,-10^9 \leq w \leq 10^9,1 \leq l \leq r \leq n。
时空限制:500ms / 512MiB。
给出一个长度为 n 的字符串 S。定义字典为 S 的所有本质不同的子串构成的集合,定义单词为字典中的字符串。
有 Q 次操作,每次操作会给出两个参数 l, r,你将会在字典中,学习以 S[l : r] 为前缀的所有单词。每次操作结束后,你需要求出有多少个单词被你学习过。
数据范围:1 \leq n, Q \leq 2 \times 10^5,1 \leq l \leq r \leq n。
时空限制:4s / 1024MiB。
给出一棵包含 n 个节点的树,以 1 为根。
定义 \mathrm{dep}_u 表示节点 u 的深度,定义 \mathrm{LCA}^{*}(l, r) 表示区间 [l, r] 中所有节点的最近公共祖先。
有 Q 次查询,每次查询给出三个整数 l, r, k,你需要求出
数据范围:1 \leq n, Q \leq 5 \times 10^5,1 \leq l \leq r \leq n,1 \leq k \leq r - l + 1。
时空限制:2s / 1024MiB。
希望能带来好运!

本文重构于 2026.06.23:以新的理解重新调整了这篇文章。
希望能带来好运!

希望能带来好运!

给出一个包含 n 个字符串的集合 D 以及一个字符串 s,你需要找出集合 D 中字典序小于 s 的字符串数量。
字符串 s 会经过 Q 次修改,每次修改会给出一个整数 k 以及一个字符 c,表示将字符串 s 从第 k 个字符开始到字符串末尾的所有字符替换成 c。每次修改完字符串 s 之后,你都需要求出集合 D 中字典序小于 s 的字符串数量。
数据范围:1 \leq n, Q \leq 10^6,1 \leq |s| \leq 10^6,字符串集合 D 的总长不超过 10^6。
时空限制:2s / 512MiB。