为了防止版权纠纷，部分内容已修改或匿名化。 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 […]
写在之前 算是开始归队了吧。感觉过去一年里文化课水平突飞猛进（飞升b(x)），算是找到了一点新的方向。 附上一张今天现拍的照片（x 访问这里 （图片背景经过处理） 因为 0727 才放假所以没做几个题（ （2024/7/28）「SNOI2017」炸弹 LOJ | Luogu 这道题第一眼看过去会想到一个暴力做法。建图，然后跑一堆 dfs 什么的。但是很明显时间复杂度是不行的（O(n^2) + O(n^2) \Rightarrow O(n^2)），于是想怎么优化。 根据我之前写过的 线段树优化建图 […]
感觉是一个很多人用的，但是搜了一圈好像没人写（ 首先是一道题。校内模拟赛的，不知道有没有原（ 在 n \times m 的平面上有 n 个互不相交的矩形（可以看作平面直角坐标系），左下角为 (x_1, y_1)，右上角为 (x_2, y_2)。然后有 q 组询问，每次询问查询给定矩形与平面上每个矩形的面积交的和。 n, m \le 5\times 10^5。 有一个朴素的 O(nm) 的做法，就是差分维护给定的矩形（修改），跑两遍前缀和，第一遍前缀和求出差分数组的原数组，第二遍是为了快速区间求和 […]
（2023/10/4）「NOIP2013 提高组」火柴排队 距离转化一下： \sum (a_i – b_i)^2 = \sum ({a_i}^2 + {b_i}^2 – 2a_ib_i) 如果需要每根火柴距离最短，只需要最大化 a_i b_i 即可。 pair<int, int> target[100005], raw[100005]; int n, c[100005]; // BIT int BIT[100005]; constexpr int lowbit […]
前言：关于今年提高 意料之中而又意料之外的挂分。感觉，之前训练了那么久，这些题在考场还是没法做出来。真就，每题都是暴力。这道题反正就是大众部分分 35 pts。我也不是那种可以化悲愤为动力的人，很难受啊，写这篇文章的时候的前一天晚上（考后晚上）哭了一会儿。其实还是对自己有期望的，但讲真期望一直不是很高。其实非常羡慕那些可以化悲愤为动力的人，但是我只能把悲愤吞下去内耗然后继续原地开摆。 个人精神状态不适合在这个场合进行太多讨论；那么既然都过去了，咱还是来看一下这个题怎么做好了！ 正文 这道题是 C […]
嗯……感觉很多人都在写中缀转后缀。 今天咱来看工程上编译器「语法分析」用得比较多的方法，「递归下降」。感觉会有所启发。 首先，表达式可以被表示为树形结构，在本题背景下是「二叉树」，这一点翻一下其他题解就可以看到了，这里不再赘述。 然后是「递归下降」对表达式进行语法分析。 最先说明一句，为了表达式的运算足够清晰，我们先考虑根据原表达式建立「表达式树」，或者更专业地，AST (Abstract Syntax Tree)，而不会在 parse 表达式时进行求值。 既然叫「递归下降」，那么肯定是逃不了递 […]
CF Link | Luogu Link 昨天比赛写的一道非常有意思的题，完赛前 5 分钟想出的解法（然后没写出来）。 主要讲的是找规律，然后没有很严谨的数学证明。 题意 定义一个对序列的操作为： 升序排序 + 去重 如果只剩一个元素就返回这个元素 将所有元素 a_i（下标从 0 开始）加上 n – i，并回到步骤 1。 有 q 次询问，每次询问修改原序列上下标为 i 的一个数，在每次修改后求出这个新序列的操作值。 解法 找规律。如果数感好并且想象力比较丰富的话，可以大概看出来一些规 […]
啊这是一篇水文 题意就是，有 N 本书，每本书 i 需要在阅读前先阅读一些依赖的书；要求以最少阅读量完成书 1 的阅读，按照满足依赖关系的阅读顺序打印出必须阅读的除书 1 以外的书的编号。 就是个拓扑排序板子，但是为了满足最小阅读量，所以跑一遍深搜把不会访问到的点排除出点集就行。 Code: void dfs(int u) { vis[u] = 1; for (auto v : G[u]) { if (!vis[v]) dfs(v); } } int main() { io_init(); ci […]
其实一开始写这玩意是因为感觉自己 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。 上树（入树）可以保证你可以从任意 区间 走到任意的 点。 然后再 […]