批处理学习笔记 发表于 2022-07-16 更新于 2024-04-13 分类于 Dumby的折腾笔记 本贴为批处理学习笔记。 别问为什么要学批处理,问就是爱折腾。 因为是折腾,所以学得很散很乱。 阅读全文 »
CF558E A Simple Task 发表于 2022-07-12 更新于 2024-04-13 分类于 Dumby的OI生涯 思路开一个 set 维护当前有哪些点是区间的左区间。 对于每个有序区间,开一个权值线段树维护,并记录一下该区间是升序还是降序。 每次排序时就将维护这些区间的线段树分裂再合并,最后查一下每棵树再输出就好了。 阅读全文 »
洛谷 P2824 排序 发表于 2022-07-11 更新于 2024-04-13 分类于 Dumby的OI生涯 洛谷P2824 [HEOI2016/TJOI2016]排序。 思路离线做法受 01 串排序的启发,我们可以二分答案,将大于等于 $mid$ 的数设为 $1$,小于的设为 $0$,然后排个序。 如果排完序后询问的 $q$ 位置的数仍为 $1$,则 $mid$ 可行。 阅读全文 »
Dsu on Tree (树上启发式合并)不是很详的解 发表于 2022-07-09 更新于 2024-04-13 分类于 Dumby的OI生涯 引子先来个例题耍耍。 给出一棵 $n$ 个节点以 $1$ 为根的树,节点 $u$ 的颜色为 $c_{u}$,现在对于每个结点 $u$ 询问以 $u$ 为根子树里一共出现了多少种不同的颜色。$n \le 2 \times 10^{5}$。(没错就是 OIWiki 上的例题。。。) 阅读全文 »
SPOJ2916 GSS5-Can you answer these queries V 发表于 2022-07-09 更新于 2024-04-13 分类于 Dumby的OI生涯 解析题目很坑,题中的子段是不能为空的。 其余就是一个比较裸的线段树维护区间最大值,在左右区间是否重合、包含上讨论一下就好了(虽然我调了快一晚上)。 阅读全文 »