准备学习扫描线的时候，发现洛谷日报上并没有关于扫描线的文章，于是心血来潮想写一篇。顺便纪念一下我马上结束的 OI 生涯。 日志 感谢@许多的帮助纠正。 前置知识 线段树或树状数组 （不会的请【模板】线段树 1 ，【模板】树状数组 1 ) 离散化 目的 先来了解一下扫描线都能做些什么： 矩形面积并 矩形周长问题 二维数点（静态区间查询类问题） B 维…

这篇文章受密码保护，输入密码才能阅读

个人认为这道题评不到蓝。 思路 根据题目中建图的性质，我们可以考虑对一个数转化成二进制的形式，并记录每一位的 $1$ 的个数，若在某一位上，有至少 $3$ 个点这一位为 $1$，那么这三个点之间都有一条边，也就是形成了一个三元环，根据数据范围，把所有数转化成二进制后最多有 $64$ 位，根据抽屉原理，当 $n> 128$ 时，一定存在一位，该…

思路 若超级马能到达棋盘上所有的点，那么超级马一定可以在 X 轴和 Y 轴上随意地移动，换句话说，假设超级马一开始位于 $(0,0)$ 超级马一定可以到达 $(1,0),(0,1),(-1,0),(0,-1)$ 这 $4$ 个点，以这 $4$ 个点为基础，超级马可以移动到任意一个他想去的地方，这时候问题就转化成了超级马经过若干次移动后能否到达上面描…

个人认为是一道比较有新意的二维数点题。 思路 因为操作一是把整棵树都染绿，之后让深度 $\ge x$ 的结点变黄，不难发现黄色节点的个数随着 $x$ 的减小而增大。 我们考虑将所有询问离线处理，按 $x$ 的大小从大到小处理每个询问。 我们预处理出所有点的子树的大小，每个节点的 dfs 序以及每个深度对应哪些节点。 我们以 dfs 序为一维，以点的…

思路 根据题意，我们不难发现题目中要求的折线最多只有 $4$ 个这店，最少只有 $2$ 个折点，至于为什么，我们看下面的几张图。 如图，当点的个数关于某条直线对称的时候，即一条直线即可将点平均分成两组，这时候只需要 $2$ 个折点即可。 若出现上图所示情况，即无法用一条边将点的个数平分，我们考虑增加一个折点，在图中划分出一个小矩形来，并判断是否存在…

思路 首先得出这道题必须离线处理。 错误思路：正序处理 因为我们已知所有操作一的信息，如果忽略操作二，根据操作一的信息可以计算出最终数组与题目中给出数组的差，这个差必须由操作二补上。 我们考虑用 $delta_i$ 记录忽略操作二后所得数组中第 $i$ 个数与最终数组中第 $i$ 个数的差，正序遍历每个操作，对于操作一用线段树直接维护，对于每个操作…

思路 我们考虑朴素的枚举做法，用一个链表暴力模拟，并判断当前的歌和上一首歌的风格的 $gcd$ 是否为 $1$ 即可，一直到一轮下来没有任意一首歌被删除为止 但这样做的话很显然会超时，我们发现有些歌在上面暴力枚举的时候被重复计算了多次，但有些歌被重复计算多次，我们考虑如何将重复的计算优化掉。 我们不难发现，判断歌曲风格的关系是按一定顺序的，而且这个…

思路 为了尽可能地减小吃巧克力的花费，我们考虑用一个堆来维护当前没有过期的巧克力中的最小值，我们考虑从最后一天开始向前枚举，并将当天没有过期的巧克力加入堆中，每天取堆的最小值，并判断数量是否耗尽即可。 但如果是从第一天开始遍历的话，这样算出来的答案是不对的，我们举一个样例： 5 3 1 4 3 2 1 1 10 5 5 15 但如果从第一天开始遍历…

思路 我们可以考虑将问题转化成一个背包问题。 我们考虑先将每个点按 $x$ 大小进行排序，但注意，排完序后的点不一定满足题目中横坐标、纵坐标值均单调不减的要求。 我们考虑按 $x$ 的大小从小到大枚举每个点，对于每个点，我们枚举当前该点前面的所有点，判断是否满足横坐标、纵坐标值均单调不减的要求，若满足，则以 $k$ 为背包最大容量，以 $x_i-x…

思路 我们考虑以每个点为起点跑一遍 dijkstra，以 $1$ 为边权，只记录所有最短距离小于等于 $k$ 的点，并重重新建一张图，在能经过至多 $k$ 次中转后到达的点之间连一条边。因为 $5 \le n \le 2500$，所以我们可以用一个二维数组来储存两个点之间是否能相互到达。 这样我们可以通过枚举 $4$ 个不同的点，判断他们是否连通且…