目录
仅有对 DS 的非平凡使用会打 tag, 如果仅仅拿线段树维护个区间加减区间和啥的就不打了.
\[\mathfrak{Defining~\LaTeX~macros\dots}\\ \newcommand{\chr}[1]{\underline{\texttt{#1}}} \]Day 1
「Ynoi 2009」「洛谷 P6109」rprmq1 ^
Link & Submission.
「Ynoi Easy Round 2021」「洛谷 P8512」TEST_152
Link & Submission.
Tag:「C.复杂度分析」
操作只有区间赋值? 立马向珂朵莉树的方向思考. 注意若模拟所有 \(n\) 次操作, 一共只有 \(\mathcal O(n)\) 次区间贡献变化, 而这些变化也仅仅是单纯的区间加减. 因此, 可以对询问的 \(r\) 扫描线, 用数据结构维护每个 \(l\) 对应的答案. 复杂度 \(\mathcal O((n+q)\log m)\).
「Ynoi 2005」「洛谷 P7907」rmscne
Link & Submission.
Tag:「C.性质/结论」
这题麻烦的地方在于, 最终的答案区间很可能有 \(l<l'\le r'<r\), 左右端点都会向内缩, 我们就没有办法固定一端做扫描线之类的工作. 这也提示我们, 应该先去思考关于合法区间的性质.
其实, "枚举端点" 是 "固定端点" 的有力方法. 对于询问 \([l,r]\), 设有最小的 \(p\), 使得 \([p,r]\) 合法. 我们在 \([l,p]\) 中枚举左端点 \(l'\), 找到此时使得 \([l',r']\) 关于 \([l',r]\) 合法的最大 \(r'\), 再求 \(r'-l'+1\) 的最大值就是答案.
通过等价转化, 我们使 \(r'\) 仅与左端点 \(l'\) 和固定端点 \(r\) 有关, 这时候就能对 \(r\) 扫描线了. 令 \(p_i\) 表示 \(l'=i\) 时最小的 \(r'\), 对于询问, 我们需要完成两个工作: 1) 求出 \(p\); 2) 求出 \([l,p]\) 中 \(p_i-i+1\) 的最大值. 对于前者, 维护方法很多, 但用 DSU 之类的小常数做法才不会被卡常. 对于后者, 可以用线段树简单维护. 于是我们得到了 \(\mathcal O((n+q)\log n)\) 的做法.
「Ynoi 2010」「洛谷 P6105」y-fast trie
Link & Submission.
Tags:「B.Tricks」「C.性质/结论」
对 \(i+j\ge C\) 的情况, 维护全局最大次大即可. 我们主要讨论 \(i+j<C\) 的情况. 设在某一时刻 \(i\) 的最优匹配数为 \(p(i)\), 显然仅有 \(p(p(i))=i\) 的 \(i+p(i)\) 可能贡献答案 (trick), 我们需要时刻维护这一双向最优匹配关系.
这里以插入的讨论为例. 设当前集合还未插入, 即将插入 \(x\). 找到 \(y=p(x),z=p(y),w=p(z)\). 若 \(y\) 存在且(\(z\) 不存在或者 \(z<x\)), 则 \((x,y)\) 为新增双向对, 在此条件下此, 若 \(z\) 存在且 \(w=y\), 则 \((y,z)\) 为被 \((x,y)\) 顶替, 将被删除的双向对. 用可删堆维护双向对贡献, std::map 或者 std::multiset 维护集合以计算 \(p\) (推荐前者, 因为 std::multiset::count 的复杂度不正确), 可以做到 \(\mathcal O(n\log n)\).
「北大集训 2021」「LOJ #3673」简单数据结构
Link & Submission.
(注意代码 L112 amx[u] += k * rig[u] 逻辑有误, rig[u] 应改为区间内 activated 的最右位置而非区间右端点. 应该能卡, 不知道为什么能过.)
Tags:「A.分治-整体二分」「A.分治-数据结构上二分」「A.数据结构-李超树」「A.数据结构-线段树」「C.细节」
自然地发现, 若所有 \(a_i\) 初始为 \(0\), 则 \(\{a_n\}\) 永远单调, 操作 1 的效果变为后缀赋值, 这时结合线段树二分, 我们可以用线段树方便地维护操作.
受此启发, 我们尝试把原问题化归到这种情况. 此时, 我们需要求出每个 \(a_i\) 第一次被取 \(\min\) 的时间 \(t_i\): \(t_i\) 之前, \(a_i\) 不会被取 \(\min\), 维护很方便; \(t_i\) 之后, 所有同 \(a_i\) 一样被取过 \(\min\) 的 \(a_j\) 构成的子序列是单调的, 可以用上面的方法维护. 这部分可以做到 \(\mathcal O(q\log n)\), 只是实现较为恶心.
最后的问题, 如何求 \(t_i\)? 注意每个操作 1 前操作 2 的次数一定, 因此对于 \(a_i\) 若其一直未被取 \(\min\), 到第 \(j\) 个操作 1 时的值可以写作 \(k_j\times i+a_i\). 整体二分, 李超树插入这些直线以划分左右子问题即可. 这部分可以做到 \(\mathcal O(n\log^2n)\).
Day 2
「北大集训 2021」「LOJ #3676」小明的树
Link & Submission.
Tags:「A.数据结构-线段树」「B.Tricks」
经典老番:
- 美丽 \(\Leftrightarrow\) 黑点构成连通块 \(\Leftrightarrow\) 第 \(i\) 次操作后, \(n-1-i=c\), \(c\) 为黑-黑边数.
- 美丽时, 白点连通块数 \(=d\), \(d\) 为黑-白边数.
- \(n-1-i\ge c\).
线段树在时间轴上维护区间最小值及其对应黑-白贡献即可. \(\mathcal O((n+m)\log n)\).
「BalkanOI 2018」「洛谷 P4786」Election ^
Link & Submission.
「HNOI 2011」「洛谷 P3215」括号修复
Link & Submission.
Tags:「A.数据结构-平衡树」「C.性质/结论」「C.细节」
对括号串的处理应该是得心应手了. 设 \(\chr (,\chr )\) 分别对应 \(1,-1\), 前缀和最小值为 \(p\le 0\), 后缀和最大值为 \(q\ge 0\), 不难证明答案为 \(\lceil-p/2\rceil+\lceil q/2\rceil\). 用一大坨平衡树维护这两个值即可. 复杂度 \(\mathcal O((n+q)\log n)\).
「HNOI 2015」「洛谷 P3242」接水果
Link & Submission.
Tags:「A.分治-整体二分」「B.DFN」
整体二分答案, 盘子对水果的贡献形式是 DFN 上的二维数点. \(\mathcal O((n+q)\log^2n)\).
「Ynoi 2010」「洛谷 P6018」Fusion tree
Link & Submission.
波奇酱剖分 定根, 每个点维护孩子们的点权集合. 难点在于对集合的整体 \(+1\).
分析发现, \(+1\) 进位的数一定是奇数, 即最低 bit 为 \(1\), 进位等价于对从次低 bit 开始的数 \(+1\), 这是一个子问题. 以 Trie 树的视角, 对 \(u\) 子树 \(+1\) 相当于交换左右子树, 然后递归向左子树. 这样就能维护了. 最终复杂度 \(\mathcal O((n+q)\log V)\).
「OurOJ #6861」party
简要题意
给定一棵含 $n$ 个点的有根树, 点有颜色. 处理 $q$ 次询问, 每次给出 $c$ 个点, 每个点在自己走向 LCA 的路径上选择相同数量的若干颜色, 颜色不能与其他点选的颜色有交. 回答最多选出的颜色总数.$n\le3\times10^5$, 颜色种类 $m\le10^3$, $q\le5\times10^4$, $c\le5$.
Tags:「B.复杂度平衡」「C.性质/结论」
我似乎写了个怪做法.
"选出颜色数量相同" "颜色不交", 若已知每个点选 \(k\) 个颜色, 则将每个点复制 \(k\) 份, 每个复制点连向原点能选择的颜色, 用 Hall 定理检查合法性. 反过来, 枚举 Hall 定理检查的集合 \(S\), 设 \(S\) 中的点总共能选择 \(c_S\) 种颜色, 则有限制 \(k\le c_S/|S|\). 只需要求出所有 \(c_S\), 取最小值即为答案.
注意 \(m\times q\times c\) 勉强能被接受, 可以直接枚举颜色, 用 \(\mathcal O(\sqrt n)\) 区间加 \(\mathcal O(1)\) 查单点的序列维护手法维护每个点祖先内的当前颜色数量, 再枚举询问和询问中的结点, 求出可以选择当前颜色的结点集合 \(S\) 暂存入 \(c_S\). 此后回答询问时, 先用 FMT 之类的东西还原出 \(c_S\), 再求答案即可.
复杂度有三部分, 大概是 \(\mathcal O(n\sqrt n+mqc+qc2^c)\), 不过规避了 std::bitset. (