冷滟泽的个人博客

2020-04-15 lengyanze 阅读(80) 评论(0)

定义 一个字符串 s 是 Lyndon Word，当且仅当 s 是其所有后缀中字典序最小的； 将字符串 s 分为若干部分 s_1s_2\cdots s_m，使得每个 s_i 都是 Lyndon 串，且 \foral...

2020-04-13 lengyanze 阅读(54) 评论(0)

为了求解这个问题，我们先考虑「静态区间不同元素种类数」的经典问题。下面是这个问题的一种常见解法： 对于一个固定的右端点 i，贪心地只考虑 i 之前每种元素最后出现的位置。按下标从左到右扫描线，用一棵线段树维护每个位...

2020-04-07 lengyanze 阅读(59) 评论(0)

持续更新中…… CF504E. Misha and LCP on Tree 给出一棵 n(n\leq 3\times 10^5) 个点的树，m(m\leq 10^6) 次询问求树上两条链的 LCP 长度。 考虑...

2020-04-03 lengyanze 阅读(41) 评论(0)

因为 10^{100} 相对于这道题要求的精度是一个很大的数，所以每个数最终在队列中的概率会趋近于一个固定的值，也就是我们要求的答案。设 g(i,S) 表示进行 i 次操作后，队列中元素为集合 S 的概率。那么当 i...

2020-03-30 lengyanze 阅读(50) 评论(0)

color 显然没有被删除的元素形成一个子区间，所以答案的规模是 O(n^2) 的。对于一种颜色，如果一个区间内部和外部都有这种颜色的元素，那么这个区间就是不合法的。对于每个元素我们可以找出包含它的不合法区间，它们的...