专栏文章

数据结构补完计划 P11900~P12000

nnoip毒瘤
个人记录参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mkdyf6rk
此快照首次捕获于
2026/01/14 19:45
上个月
此快照最后确认于
2026/01/14 19:45
上个月
查看原文
计划逐步做完所有公开的以数据结构为主的题目，涉及到做法超出目前能力（如高级字符串）的以及难度低（紫以下）的会被跳过。
难度评测分为：下位紫，中位紫，上位紫，下位黑，中位黑，上位黑，彩。

P11901 数组的划分

3min：这才看到数据随机，每次贪心选最长的子区间是最优的，于是可以用弹飞绵羊的套路，LCT 维护后继。由于数据随机，所以每次匹配的长度最多是 O(log⁡n)O(\log n) 的，可以暴力预处理所有长度 O(log⁡n)O(\log n) 的初始数组区间的哈希，每次 link cut 的时候花费 O(log⁡n)O(\log n) 的时间找到具体 link 到哪里。
总时间复杂度 O((n+m+q)log⁡n)O((n+m+q)\log n)。
难度评测：下位紫（LCT 模板太难）。

P11923 [PA 2025] 砖块收集 / Zbieranie klocków

10min：2×22\times2 的肯定删不了，然后画各种奇怪图形看看什么样的能删。
15min：2×22\times2 的是被完全保护的，然后发现只有连接两个被完全保护的区域的折线部分不能删，而且这个折线还必须像围棋的征子一样一直拐弯。
16min：直接对斜率正负的 4545 度维护两种线段树，每次修改最多影响 O(1)O(1) 个 2×22\times2 位置的保护性，以及 O(1)O(1) 个斜线的保护性，然后在线段树上二分即可。
总时间复杂度 O(k+qlog⁡n)O(k+q\log n)。
难度评测：和数据结构没什么关系，中位紫？

P11930 [PA 2025] 吃树叶 / Liście

之前看过。我 2021 年都出过 3dmq 了，你们 2025 年出 2dmq 是几个意思。
难度评测：下位紫。

P11945 [KTSC 2025] 军事基地 / safezone

之前看过，不过忘了怎么做了。
4min：考虑扫描线优化建图，维护一棵线段树，然后每次就是插入一个区间，要将和这个区间有交的区间全部都连边。
用线段树拆区间之后，用标记永久化讨论结点上下关系的套路，对于新加入的区间，递归过程中经过的 O(log⁡n)O(\log n) 个结点上的标记都会和这个区间合并。但是实际上我们只需要对一个结点，随便挑一个标记与这个区间合并就行，因为一个结点的多个标记之前已经维护了连通性。
现在的问题就是如何高效删除一个结点的标记，这里因为随便维护任何一个标记就行，所以很简单，可以用链表，或者用对顶堆的思路，维护两个队列，一个是插入队列一个是删除队列，每次删除就往删除队列里面插入元素，然后 while 队列头相同 pop 就行。
然后的问题就是现在只对被插入的标记，考虑了其祖先标记和其的贡献，没有考虑子树内标记的贡献。
这个我们反着做一遍扫描线，子树内的标记就会被该标记更晚打上，就可以计算这部分贡献了。
最后 DFS 一遍图求连通性即可。
总时间复杂度 O(nlog⁡n)O(n\log n)。
难度评测：中位紫。

P11947 [KTSC 2025] 可爱区间 / maxsum

5min：推一下条件：[l,r][l,r] 是最大子段和的条件是什么。
  1. [1,l−1][1,l-1] 的所有后缀和 ≤0\le0。
  2. [r+1,n][r+1,n] 的所有前缀和 ≤0\le0。
  3. [l,r][l,r] 的所有前缀和 ≤0\le0。
  4. [l,r][l,r] 的所有后缀和 ≤0\le0。
1,21,2 可以对每个 ll 每个 rr，维护出一个 0101 值，表示对于这个 ll 这个 rr，能否作为合法区间的左或者右端点。
3,43,4 可以对每个 ll 每个 rr 用线段树上二分来处理，对每个 l,rl,r，合法的另一个端点一定是一个区间。
10min：刚刚少算了一种情况，还需要：
  1. [l,r][l,r] 的区间和比 [1,l−1][1,l-1] 的最大子段和大。
  2. [l,r][l,r] 的区间和比 [r+1,n][r+1,n] 的最大子段和大。
对固定的每个 l,rl,r，合法的另一个端点显然也是连续的一个区间。
把每个线段变成补集，于是现在变成有一堆横着竖着的线段，每次询问矩形内有多少位置没有被任何线段覆盖，直接扫描线维护矩形面积并即可。
16min：发现还是做错了一个地方，因为是 [l,r][l,r] 的区间和比 [1,l−1][1,l-1] 的最大子段和大，所以实际上是要求值域的一个区间限制，和序列的区间限制没法共存。
继续研究题目性质，发现固定 ll，只有 [l,i][l,i] 构成前缀和 max⁡\max 的那些 ii 才是合法的，不然违背了前面的一些条件，于是我们维护出 [l,i][l,i] 的前缀 max⁡\max 单调栈，每次相当于只有某个 ii 的区间是符合条件的。
这里虽然我们发现只有单调栈位置是合法的，但是因为同时有 ll 和 rr 的限制，所以实际上我们还需要放宽限制，不管每个点是否在单调栈上了，因为不在单调栈上的点会被前面的条件排除。于是我们在单调栈数据结构上查出了对固定的 ll 来说合法的 ii 区间使得 [l,i][l,i] 不违背 55 条件，对固定的 rr 来说合法的 ii 区间使得 [i,r][i,r] 不违背 66 条件。
至此所有条件都可以表示为一条横线或者竖线，再套用 10min 的矩形面积并即可。
总时间复杂度 O((n+q)log⁡n)O((n+q)\log n)。
难度评测：下位黑。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...