不行了，语言开始变机械化了 TAT 还有几道题没写完 [POI2015] PUS / Pustynia 给定一个长度为 n 的正整数序列 a，每个数都在 1 到 10^9 范围内，告诉你其中 s 个数，并给出 m 条信息，每条信息包含三个数 l,r,k 以及接下来 k 个正整数 t_i，表示 a_l, a_{l+1}, \ldots, a_{r-1}, a_r 里这 k 个数中的任意一个都比任意一个剩下的 r-l+1-k 个数大（严格大于，即没有等号）。 请任意构造出一组满足条件的方案，或者判断 […]
为了防止版权纠纷，部分内容已修改或匿名化。 0818A 大意是给你一个数组，然后每次查询给区间加上/减去一个固定数值（保证修改后数组严格单调递增），查询是否包含一个下标等于值的数（即 a_i = i）。 然后发现 a_i – i 也是单调的，然后可以打懒标记（我用的线段树）然后二分。 struct Sg { struct { int lz, val; } tr[MAXN * 4]; void build(int l, int r, int p = 1); inline void pu […]
前两天给 hljs 修内存泄漏问题的时候仔细翻了一下 MDN，发现一个有点意思的东西，就是这个一次性的事件侦听器。 换言之，传统的事件侦听器的 cleanup 是这样的： /** @param e {Event} */ function listener(e) { /* … */ window.removeEventListener(‘event’, listener) } window.addEventListener(‘event’, listener) 在 Chrome 55+ / S […]
内存泄漏的整体分析在这个 issue comment 里面进行了概括，但是其实说明不是很完全。 咱再来手动说明一下吧。rehype-highlight 的上游库 lowlight 使用 highlight.js 进行代码高亮，使用 hljs 提供的 newInstance 方法创建多个 HLJS 实例。理论上来说这些实例在不使用之后应当被垃圾回收，但是事实上这么美好的愿景并没有实现，原因就是 newInstance 方法的实现偷懒了，导致每次都会执行 window.addEventListene […]
写在之前 算是开始归队了吧。感觉过去一年里文化课水平突飞猛进（飞升b(x)），算是找到了一点新的方向。 附上一张今天现拍的照片（x 访问这里 （图片背景经过处理） 因为 0727 才放假所以没做几个题（ （2024/7/28）「SNOI2017」炸弹 LOJ | Luogu 这道题第一眼看过去会想到一个暴力做法。建图，然后跑一堆 dfs 什么的。但是很明显时间复杂度是不行的（O(n^2) + O(n^2) \Rightarrow O(n^2)），于是想怎么优化。 根据我之前写过的 线段树优化建图 […]
其实一开始写这玩意是因为感觉自己 lambda 写得很好看（ HDU 3333 Turing Tree link aka 「HH 的项链」，但是维护的东西不一样，题意也有一些细微的差别。 题目大意是说，有 Q 次询问，每次询问查询区间 [l, r] 之间不重复的数字之和。没有修改操作。 既然没有修改那不是离线然后乱搞（ 考虑离线对所有询问以区间右端点为关键字进行升序排序。然后从左到右遍历数据。 见图。上面一行是线段树的更改，下面的是数据。 记录一个 \text{last} _ i，用来表示上次 […]
感觉挺好玩的就写一个。 例题：CF786B 题目大意是，给定 q 次操作，有 3 种： 连边 u\to v 连边 u \to [l, r] 连边 [l, r] \to u 然后要跑一个最短路。那么很显然的是，如果你暴力建边，时间复杂度 O(nq) 显然会超时。那么这个时候可以考虑线段树优化建边。 拿有 5 个节点的图举例子。 先来说怎么做。 首先，显然，你需要一棵线段树。 你需要根据这棵线段树的 父子关系 来建边，并且权值为 0。 上树（入树）可以保证你可以从任意 区间 走到任意的 点。 然后再 […]
本文是 洛谷MYOI月刊【7月刊】 的一篇文章。推荐大家去看看。我写的（x） 图床使用的是 sm.ms，大陆访问有点不稳定。 0. 写在前面 本文的每一个章节有一个「推荐阅读」标记，根据读者对不同技术栈、工具的了解程度进行了区分。\small\colorbox{#128e5a}{\color{white}Tool name} 代表「不熟悉/没用过」，\small\colorbox{#3173B3}{\color{white}Tool name} 代表「有一些相关了解，但只会基础操作」，\smal […]
题目传送门 RMJ 传送门 题意简述 输入一个字符串，要删掉原字符串中左右匹配的括号及其中的内容。 例如 qwq(qwq)(quq(Q)AQ 的结果就是 qwq(quqAQ。 思路分析 赛时情况：先写了个括号匹配，然后发现需要标记被删除的区间。拿线段树糊了一个版本，交上去会 TLE，最后也不知道怎么就想到了一个这么可爱的珂朵莉树。然后 AC。上分（x） 本题可以使用「珂朵莉树 + 栈」解决。使用栈进行括号匹配，同时存储上一个左括号出现的位置。若出现右括号，则进行 assign 操作，以标记需要被 […]
题目传送门 题目简述 给定一张无向图和数列 X, Y。 有 K 次询问，每次询问需要判断在询问的 u, v 之间建边之后，判断「对于所有 X_i 和 Y_i 之间都不存在路径」是否成立。 保证原图不存在 X_i, Y_i 之间有路径。 思路分析 容易发现，在同一个连通块中的所有点都存在相互可达的路径。如果新加入的边连接了两个连通块，那么这两个连通块之间的所有点就都存在路径相互可达。 因此，对于每一对 X_i, Y_i，只需判断「新加入的边是否连通了这两个点所在的连通块」。 可以用 map 来实现 […]