冷滟泽的个人博客

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 阅读(40) 评论(0)

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

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

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

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

shortest 先求出这张 DAG 的拓扑序。考虑删掉一个节点后从 S 到 T 的最短路，它的构成一定是 S + 一些拓扑序递增的节点 + 一条拓扑序跨过被删掉节点的边 + 一些拓扑序递增的节点 + T。那么这条路...