数据结构

洛谷题库 P8868 [NOIP2022] 比赛

本文记号可能稍显凌乱,但都能在题面或者前文中找到定义。

部分分

20 pts\text{20 pts}n,Q3000n,Q\leq 3000

考虑枚举所有 O(n2)\newcommand\bigO{\operatorname{O}}\bigO(n^2) 个区间,预先计算它们本身的答案。记 ga(l,r)=max{ailir}gb(l,r)=max{bilir}\begin{aligned}g_a(l,r)&=\max\{a_i\mid l\leq i\leq r\}\\g_b(l,r)&=\max\{b_i\mid l\leq i\leq r\}\end{aligned},则做前缀和 s(l,r)=i=lrga(l,i)gb(l,i)s(l,r)=\sum_{i=l}^{r}g_a(l,i)g_b(l,i),对于询问 [ql,qr][\text{ql},\text{qr}] 只需回答 i=qlqrs(i,qr)\sum_{i=\text{ql}}^{\text{qr}}s(i,\text{qr}) 即可。

n,Qn, Q 同阶,时空复杂度 O(n2)\bigO(n^2)(更多…)

More
  • 2022年12月8日

堪堪能接受的一场。前两题一个半小时左右做完,后两题实在没什么思路,打完所有可能的暴力之后跑路了。

他们告诉我题目名称可以从上到下连起来读。

一句话题解

A – (种)菜

可以发现,假若同时有 ai,ai+1\newcommand{\bigO}{\operatorname{O}}a_i,a_{i+1}ai+1,ai+2a_{i+1},a_{i+2} 都可合并,则取 ai,ai+2a_i, a_{i+2} 中任意一个合并之后,质因数集合总是变为原来的超集,另外一项仍可合并。

故而可以贪心合并所有合法的邻项,最终检查是否仅剩一项即可。注意到 [1,700][1,700] 仅含 125125 个质因数,故可以用 std::bitset 保存每一项的质因子集合。复杂度 O(128nω)O(\frac{128n}{\omega})赛时竟然还开了数组保存每个质因子的实际指数! (更多…)

More
  • 2022年10月26日

CodeForces Round #502 Problem G – The Tree

这是lty数据结构专题里唯二自己做出来的题目中的一道。

如果不包含“将 xx 的子树全部染白”的操作,应当怎样处理?

题目所给操作可以这样转述:令 xx 为本次染色操作的节点。若 xx 为白色,则立刻染黑并退出;否则我们找到其子树中的,与 xx 相连的黑色连通块,则对于每个连通块底部节点,若其不是叶子节点,我们将其儿子染黑。

由于本题的树没有特殊性质,且将来加入回退操作,故而难以维护整个连通块以及其叶子节点。因此,我们可以从“在何种情况下,节点 xx 被染黑”的方向考虑。

显然,只有从在 xx 到根的路径上的节点开始的染色操作,才可能波及到 xx。假如最终 xx 被染黑的一瞬,它被包含在了以 comprt\text{comprt} 为根的连通块中。令链 comprt,x\langle\text{comprt}, x\rangle{x1,x2,,xn},x1=comprt,xn=x\left\{x_1,x_2,\dots,x_n \right\},x_1=\text{comprt},x_n=x,那么自然想到,一种一定合法的染色序列是 {y1,y2,,yn}\{y_1,y_2,\cdots,y_n\},其中有 k[1,n]Z,yk{x1,,xk}\forall k \in [1, n] \cap \mathbb{Z},y_k \in \{x_1,\cdots,x_k\},也即我们每一步都在该连通块内部,并将连通块的最大深度推进一层

这种序列确实合法(它是充分条件),但这真的是 xx 被染黑的必要条件么? (更多…)

More
  • 2022年7月16日

洛谷题库 P4770 [NOI2018] 你的名字

本题考查对后缀数组或后缀自动机诸多性质综合、全面的应用,以及利用可持久化数据结构查询历史区间极值的方法。

也就是说,大体思路只花费一小时不到,去掉一个 log\log 却耗了我一天多……

@XZC__Bobby 花了 33 小时不到就用 SA 暴切了!!%%%

“双指针”扫描求串 TT 的每个前缀在 SS 中匹配的最长子串

在任何时刻,SAM 的状态转移函数会将某字符串引向串 SS 中的等价 endpos\mathrm{endpos} 状态。根据 endpos\mathrm{endpos} 和 parent tree 的性质,我们可以对前缀 T[1k],k{1,2,,T}T[1\cdots k], k \in \{1, 2,\cdots, |T|\} 依次求出其最长的作为 SS 的子串出现的后缀。 (更多…)

More
  • 2022年7月9日

一道让我做得相当高兴的题目。

原题链接 (这是付费比赛。)

题意简述

给定长度为 nn 的序列 aa。定义函数 f(S)=TSF2(sTs)f(S)=\sum\limits_{T\subseteq S} F^2(\sum_{s\in T} s),也即“对于 SS 的所有子集,求 F(子集所有元素之和)的平方F(\text{子集所有元素之和})\text{的平方} 之和”。其中 F(x)F(x) 为斐波那契数列的第 xx 项。有F(0)=0,F(1)=1,F(x)=F(x1)+F(x2)(x>1)F(0)=0, F(1)=1, F(x)=F(x-1)+F(x-2) (x > 1)

你需要支持以下操作,操作总数为 mm

1 x y:将 axa_x 修改为 yy

2 l r:输出 i=lrj=irf({ai,ai+1,,aj})\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}f(\{a_i, a_{i+1}, \cdots, a_{j}\}),对 998244353998244353 取模。

数据范围:对于 \text{50%} 的数据,有 n,m100n,m\leq 100;对于 \text{70%} 的数据,有 n,m1000n,m\leq 1000;对于 \text{100%} 的数据,有 n,m105,ai105n,m\leq 10^5, a_i \leq 10^5

(更多…)

More
  • 2022年6月20日

CodeForces Round #755 Div.2 F / Div.1 D Serious Business

此题整整困了我一天半,耗费了好几张草稿纸。实在走投无路,翻看题解,却发现正解曾经近在咫尺。有必要稍作整理。

考虑DP。

错误转移1

这道题与清理班次(《算法竞赛进阶指南》上的一道例题)过于相似,都是“给定一些段落[lp,rp][l_p, r_p],选择其中一些完整覆盖[l0,r0][l_0,r_0],求最小花费”的形式。记上述花费为f(l0,r0)f(l_0, r_0)。但本题与原题不一样之处在于其起点和终点是任意给定的。我的第一反应是枚举在x2x_2位置从第22行转到第33行,利用数据结构维护所有x1x2x_1\leq x_2,在x1x_1转移到第二行,解锁到达x2x_2的最小代价。对于各行前缀和,我们可以利用线段树或树状数组维护。同时我们也知道可以利用数据结构优化在O(nlogn)\mathrm{O}(n \log n)的时间内,计算出对于一个固定的起点l0l_0,所有f(l0,r0),r0[l0,n],p,rp=r0f(l_0, r_0), r_0 \in [l_0, n], \exists p, r_p=r_0的值。 (更多…)

More
  • 2022年3月8日

UPD 02.15:更新了区间操作部分。

约莫半月前练习专题时,发现几道解法多样的题目,其中需要运用一些中高级数据结构。苦于之前没有学习过平衡树,便挑选了一种易于上手、实现简单的平衡树学习,也即FHQ Treap。由11年国家队队员范浩强发明。

为书写方便,文章中可能将直接使用pp代指某节点的随机权值,val\text{val}代指节点关键码(即记录的数值),hh代指树高,siz\text{siz}代指子树大小,cnt\text{cnt}代指节点副本数(相同关键码的节点),rt\text{rt}存储根节点编号。

(更多…)

More
  • 2022年2月15日

终于体会到了“看了题解都可能写不出来”的绝望了——CF925E May Holidays

自以为已经对“分块”的思想有了一定掌握,到头来发现自己还只会最基本的、应用最广泛的值域分块。只是题见得不够多罢了。

考虑一种实际操作中不会使用的求区间第kk的算法。设块长为SS,我们将序列分成O(nS)\mathrm{O}(\dfrac{n}{S})块,每一块内直接对元素排序对于一个询问[l,r][l, r],我们二分答案。猜测答案为dd,在中间的每一整块内二分出d\leq d的元素数量,两侧暴力查找。这样的复杂度是O(lenSlog2n+Slogn)\mathrm{O}(\dfrac{len}{S} \log^2 n+S \log n)的,其中lenlen代表区间长。

这告诉我们,分块的目的不仅可以让较大的值域范围内的统计变得更高效,还可以使得元素(部分)有序,适用范围更加广泛。就连分块这种暴力数据结构使用时都需灵活变通,其他算法又何尝不是如此。

(更多…)

More
  • 2022年1月18日

昨天考试完成T4时,明明想出了正解,但又以为二叉堆时间复杂度过高不敢实现……白白浪费了几十分钟时间。事后实现,发现完全没有技术上的问题。

具体来讲,通过同时保存指向每个元素在堆中当前位置的指针,可以O(logn)\mathrm{O}(\log n)地修改和删除特定节点,以及常规的O(logn)\mathrm{O}(\log n)的弹出栈顶、插入等操作,O(1)\mathrm{O}(1)地查询堆顶元素。

下面就以动态修改无向图中每个点的度并查询最小度的点为例实现一个这样的二叉堆。

(更多…)

More
  • 2021年12月12日