我的文章

    我的文章

    • 「Ynoi2011」成都七中

      Luogu P5311

      给出一棵包含 nn 个点的树,每个节点有一种颜色 cic_i。

      有 mm 次查询,每次查询给出三个参数 l,r,xl, r, x,表示询问只保留编号在 [l,r][l, r] 范围内的点时,xx 所在连通块的颜色种类数。

      数据范围:1≤n,m≤1051 \leq n, m \leq 10^5,1≤ci≤n1 \leq c_i \leq n,1≤l≤x≤r≤n1 \leq l \leq x \leq r \leq n。

      时空限制:11s / 250250MiB。

    • 「2025 杭电多校 2」1004. 子串的故事(2)

      HDU 7994

      对于一个包含字符串 s1,s2,…,sks_1, s_2, \dots, s_k 的字符串可重集 TT,定义 TT 的价值为

      ∑1≤i<j≤kLCP(si,sj)\sum\limits_{1 \leq i < j \leq k} \mathrm{LCP}(s_i, s_j)

      给出一个长度为 nn 的字符串 SS,下标从 11 到 nn。有一个初始为空的字符串集合 TT。

      有 mm 次操作,每次操作给出两个正整数 l,rl, r (1≤l≤r≤n1 \leq l \leq r \leq n),你需要将字符串 S[l:r]S[l : r] 的所有前缀都加入集合 TT。形式化地,对于所有 l≤i≤rl \leq i \leq r,你需要将 S[l:i]S[l : i] 加入集合 TT。

      每次操作过后,你都需要求出此刻集合 TT 的价值。答案对 109+710^9 + 7 取模。

      数据范围:1≤n,m≤1051 \leq n, m \leq 10^5。

      时空限制:88s / 512512MiB。

    • 「Ynoi2006」rldcot

      Luogu P7880

      给出一棵包含 nn 个节点的树,以 11 为根,边带权。

      定义 depx\mathrm{dep}_x 表示节点 xx 到根的简单路径上的边权和。

      有 QQ 次查询,每次查询给出两个参数 l,rl, r,对于所有满足 l≤i,j≤rl \leq i, j \leq r 的二元组 (i,j)(i, j),你需要求出有多少种不同的 depLCA(i,j)\mathrm{dep}_{\mathrm{LCA}(i, j)}。

      数据范围:1≤n≤1051 \leq n \leq 10^5,1≤Q≤5×1051 \leq Q \leq 5 \times 10^5,−109≤w≤109-10^9 \leq w \leq 10^9,1≤l≤r≤n1 \leq l \leq r \leq n。

      时空限制:500500ms / 512512MiB。

    • 「2025 ICPC 武汉邀请赛」J. Dictionary

      QOJ 10745

      给出一个长度为 nn 的字符串 SS。定义字典为 SS 的所有本质不同的子串构成的集合,定义单词为字典中的字符串。

      有 QQ 次操作,每次操作会给出两个参数 l,rl, r,你将会在字典中,学习以 S[l:r]S[l : r] 为前缀的所有单词。每次操作结束后,你需要求出有多少个单词被你学习过。

      数据范围:1≤n,Q≤2×1051 \leq n, Q \leq 2 \times 10^5,1≤l≤r≤n1 \leq l \leq r \leq n。

      时空限制:44s / 10241024MiB。

    • 「NOIP2024」树上查询

      Luogu P11364

      给出一棵包含 nn 个节点的树,以 11 为根。

      定义 depu\mathrm{dep}_u 表示节点 uu 的深度,定义 LCA∗(l,r)\mathrm{LCA}^{*}(l, r) 表示区间 [l,r][l, r] 中所有节点的最近公共祖先。

      有 QQ 次查询,每次查询给出三个整数 l,r,kl, r, k,你需要求出

      max⁡l≤l′≤r′≤r∧r′−l′+1≥kdepLCA∗(l′,r′)\max\limits_{l \leq l' \leq r' \leq r \land r' - l' + 1 \geq k} \mathrm{dep}_{\mathrm{LCA}^{*}(l', r')}

      数据范围:1≤n,Q≤5×1051 \leq n, Q \leq 5 \times 10^5,1≤l≤r≤n1 \leq l \leq r \leq n,1≤k≤r−l+11 \leq k \leq r - l + 1。

      时空限制:22s / 10241024MiB。

    • 2025 FJCPC 云游记

      希望能带来好运!

    • LaTeX 小记

      本文重构于 2026.06.23:以新的理解重新调整了这篇文章。

    • 2024 CCPC Final 游记

      希望能带来好运!

    • 2025 ICPC 西安邀请赛游记

      希望能带来好运!

    • 「gym103483」C. How Many Strings Are Less

      gym103483 C

      给出一个包含 nn 个字符串的集合 DD 以及一个字符串 ss,你需要找出集合 DD 中字典序小于 ss 的字符串数量。

      字符串 ss 会经过 QQ 次修改,每次修改会给出一个整数 kk 以及一个字符 cc,表示将字符串 ss 从第 kk 个字符开始到字符串末尾的所有字符替换成 cc。每次修改完字符串 ss 之后,你都需要求出集合 DD 中字典序小于 ss 的字符串数量。

      数据范围:1≤n,Q≤1061 \leq n, Q \leq 10^6,1≤∣s∣≤1061 \leq |s| \leq 10^6,字符串集合 DD 的总长不超过 10610^6。

      时空限制:22s / 512512MiB。