置顶文章

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...

精选分类

题解

2 篇文章

文章列表

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 显然是建虚树出来。 看到修改路径上的颜色，显然可以用树剖维护。 建虚树时，刚好可以利用树剖得到两个点之间的所有颜色。 然后问题是建虚树出来之后考虑怎么做。 首先看到路径上这三个字，可以考虑点分治。 #...