置顶文章

1.2k 1 分钟

# 日常摸鱼 记录一些刷的水题以及伞兵错误。 # 2022 # 2022 - 01 洛谷 P2572 [SCOI2010] 序列操作 原题。线段树水题,首先肯定要维护 111 的状态。对于取反的操作,只要再维护 000 的状态就可以了,提交记录。 洛谷 P2486 [SDOI2011] 染色 原题。树剖模板,直接维护区间左端点、右端点和颜色段数即可,提交记录。 不过一开始写错了。对于查询,需要 uuu 和 vvv 两个点一起往上爬。我的维护方式是 resu 表示 u→LCAu\to \text{LCA}u→LCA 的路径, resv 表示 LCA→v\text{LCA} \to...

精选分类

文章列表

3.6k 3 分钟

# Solution 原题 # Point 1 建图 首先是如何建模 AAA 的最长上升子序列,可以参考这道题。 简单描述一下,就是对于每一个位置 iii,求出以 AiA_iAi​ 结尾的最长上升子序列长度 dpidp_idpi​,此时最长上升子序列长度 lenlenlen 就是 max⁡{dpi}\max\{dp_i\}max{dpi​}。 然后将满足 dpj=dpi+1dp_j=dp_i+1dpj​=dpi​+1,Aj>AiA_j>A_iAj​>Ai​,j>ij>ij>i 的 jjj 与 iii...
5.6k 5 分钟

# description 来源:洛谷 P4242 给你一棵树,每个节点都有颜色,有两种操作: 指定其中 kkk 个节点,对于每个节点,计算它 到每个给定的节点的路径上颜色的段数 的和。 修改一条路径上所有节点的颜色。 # solution 首先看描述就可以识算法了。 看到 ∑k≤2×105\sum k \le 2\times10^5∑k≤2×105 显然是建虚树出来。 看到修改路径上的颜色,显然可以用树剖维护。 建虚树时,刚好可以利用树剖得到两个点之间的所有颜色。 然后问题是建虚树出来之后考虑怎么做。 首先看到路径上这三个字,可以考虑点分治。 #...